1
Mô phỏng các thuật toán sort bằng C++ Tue Jun 11, 2013 11:49 am
 |  |  |
 |  | |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
- Code:
// Thuat toan sap xep thuong
#include <iostream>
#include <windows.h> //thu vien do hoa
#include <stdio.h> //system("cls");
#include <time.h>
#include <stdlib.h>
#include <conio.h>
using namespace std;
void output(int *a,int n,int j);
void banner();
/**********************************************************************************/
void textcolor(WORD color)
{
HANDLE hConsoleOutput;
hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_SCREEN_BUFFER_INFO screen_buffer_info;
GetConsoleScreenBufferInfo(hConsoleOutput, &screen_buffer_info);
WORD wAttributes = screen_buffer_info.wAttributes;
color &= 0x000f;
wAttributes &= 0xfff0;
wAttributes |= color;
SetConsoleTextAttribute(hConsoleOutput, wAttributes);
}
void textbackground(WORD color)
{
HANDLE hConsoleOutput;
hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_SCREEN_BUFFER_INFO screen_buffer_info;
GetConsoleScreenBufferInfo(hConsoleOutput, &screen_buffer_info);
WORD wAttributes = screen_buffer_info.wAttributes;
color &= 0x000f;
color <<= 4;
wAttributes &= 0xff0f;
wAttributes |= color;
SetConsoleTextAttribute(hConsoleOutput, wAttributes);
}
void gotoxy(short x,short y)
{
HANDLE hConsoleOutput;
COORD Cursor_an_Pos = { x,y};
hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hConsoleOutput , Cursor_an_Pos);
}
/****************************************************************************/
void checkbox(int n)
{
system("cls");
banner();
textbackground(15);
for(int i=0;i<n;i++)
{
gotoxy((i+2)*4,10);cout<<" ";
}
}
int *capphat(int n)
{
int *a=new int[n];
return a;
}
void input(int *&a,int &n)
{
srand(time(NULL));
do
{
cout<<"Nhap vao so luong phan tu: ";cin>>n;
}while(n>17);
a=capphat(n); //cap phat bo nho cho con tro
checkbox(n);
textcolor(0);
for(int i=0;i<n;i++)
a[i]=rand()%10;
output(a,n,0);
}
void output(int *a,int n,int j)
{
textbackground(15);
textcolor(0);
for(int i=j;i<n;i++)
{
gotoxy((i+2)*4,10);cout<<" "<<a[i]<<" ";
}
textbackground(0);
textcolor(15);
}
void mophong(int i)
{
gotoxy(((i+2)*4)+1,12);cout<<"^";
Sleep(1000);
gotoxy(((i+2)*4)+1,12);cout<<" ";
}
void tomau(int i,int b,int mau)
{
textbackground(mau);
textcolor(0);
gotoxy(((i+2)*4),10);cout<<" "<<b<<" ";
textbackground(0);
textcolor(15);
}
void tomau2(int n,int a[])
{
textbackground(8);
textcolor(0);
for(int i=0;i<=n;i++)
{
gotoxy(((i+2)*4),10);cout<<" "<<a[i]<<" ";
}
textbackground(0);
textcolor(15);
}
void xoamophongwapxang(int i,int k,int so,int z)
{
textbackground(0);
textcolor(0);
gotoxy((z==0)?(i-k+3)*4:(i+k+1)*4,(so==0)?12:8);cout<<" ";
}
void mophongwapxang(int *a,int i,int k,int so,int z)
{
textbackground(11);
gotoxy((z==0)?(i-k+3)*4:(i+k+1)*4,(so==0)?12:8);cout<<" "<<a[i]<<" ";
}
void xoamophongwaplen(int i,int k,int so)
{
textbackground(0);
textcolor(0);
gotoxy(((i+2)*4),(so==0 )?10+k:10-k);cout<<" ";
}
void mophongwaplen(int *a,int i,int k,int so)
{
textbackground(11);
gotoxy(((i+2)*4),(so==0)?10+k:10-k);cout<<" "<<a[i]<<" ";
}
void swap(int &c,int &d,int *a,int i,int n,int min)
{
int k=0;
while(k!=2)
{
xoamophongwaplen(min,k,0);
xoamophongwaplen(i,k,1);
k++;
mophongwaplen(a,min,k,0);
mophongwaplen(a,i,k,1);
Sleep(500);
}
int l=0;
while((min-l)>=i)
{
xoamophongwapxang(min,l,0,0);
xoamophongwapxang(i,l,1,1);
l++;
mophongwapxang(a,min,l,0,0);
mophongwapxang(a,i,l,1,1);
Sleep(500);
}
xoamophongwapxang(min,l,0,0);
xoamophongwapxang(i,l,1,1);
int temp;
temp=c;
c=d;
d=temp;
output(a,n,i);
}
void duongvien()
{
for(int i=0;i<80;i++)
{
gotoxy(i,6);cout<<"-";
}
}
void selection_sort(int *a,int n)
{
textbackground(0);
textcolor(15);
duongvien();
gotoxy(20,4);cout<<"Mo Phong Thuat Toan Selection Sort";
int min;
for(int i=0;i<n-1;i++)
{
min=i;
gotoxy(((i+2)*4)+1,12);cout<<"^";
for(int j=i+1;j<n;j++)
{
tomau(j,a[j],10);
if(a[j]<a[min])
{
Sleep(500);
tomau(min,a[min],(min!=i)?10:15);
min=j;
tomau(j,a[j],11);
}
Sleep(1000);
}
Sleep(500);
swap(a[i],a[min],a,i,n,min);
mophong(i);
gotoxy(((i+2)*4)+1,12);cout<<" ";
tomau2(i,a);
}
}
void tomau3(int j,int n,int a[])
{
textbackground(8);
textcolor(0);
for(int i=j;i<n;i++)
{
gotoxy(((i+2)*4),10);cout<<" "<<a[i]<<" ";
}
textbackground(0);
textcolor(15);
}
void boble_sort(int *a,int n)
{
textbackground(0);
textcolor(15);
duongvien();
gotoxy(20,4);cout<<"Mo Phong Thuat Toan boble Sort";
int j=0;
for(int i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
gotoxy((j+2)*4+1,12);cout<<"^";
mophong(j+1);
if(a[j]>a[j+1])
swap(a[j],a[j+1],a,j,n,j+1);
gotoxy((j+2)*4+1,12);cout<<" ";
}
}
}
void exchage_sort(int a[],int n)
{
textbackground(0);
textcolor(15);
duongvien();
gotoxy(20,4);cout<<"Mo Phong Thuat Toan Exchage Sort";
for(int i=0;i<n;i++)
{
gotoxy((i+2)*4+1,12);cout<<"^";
for(int j=i+1;j<n;j++)
{
mophong(j);
if(a[i]>a[j])
{
swap(a[i],a[j],a,i,n,j);
gotoxy((i+2)*4+1,12);cout<<"^";
}
}
gotoxy((i+2)*4+1,12);cout<<" ";
tomau2(i,a);
}
}
void mophonginsertion(int a[],int i,int j,int n)
{
int k=0;
while(k!=2)
{
textbackground(0);
textcolor(0);
gotoxy(((i+2)*4),10+k);cout<<" ";
k++;
textbackground(11);
gotoxy(((i+2)*4),10+k);cout<<" "<<a[(j<0)?0:j]<<" ";
Sleep(500);
}
output(a,n,0);
textbackground(0);
textcolor(0);
gotoxy(((j+2)*4),10);cout<<" ";
int l=0;
while((i-l)>=j)
{
textbackground(0);
textcolor(0);
gotoxy((i-l+3)*4,12);cout<<" ";
l++;
textbackground(11);
gotoxy((i-l+3)*4,12);cout<<" "<<a[(j<0)?0:j]<<" ";
Sleep(500);
}
textbackground(0);
textcolor(0);
gotoxy((i-l+3)*4,12);cout<<" ";
}
void insertion_sort(int a[],int n)
{
textbackground(0);
textcolor(15);
duongvien();
gotoxy(20,4);cout<<"Mo Phong Thuat Toan Insertion Sort";
int temp;
int j;
for(int i=1;i<n;i++)
{
gotoxy((i+2)*4+1,12);cout<<"^";
temp=a[i];
j=i-1;
while(j>=0 && temp<a[j])
{
a[j+1]=a[j];
j--;
output(a,n,0);
mophong(j);
}
gotoxy((i+2)*4+1,12);cout<<" ";
mophonginsertion(a,i,j,n);
a[j+1]=temp;
output(a,n,0);
}
}
void banner()
{
textbackground(4);
textcolor(11);
for(int i=0;i<80;i++)
{
gotoxy(i,0);cout<<" ";
}
gotoxy(25,0);cout<<"tvt-12cth1 laptrinhc.forumvi.com\n\n";
textbackground(0);
textcolor(15);
}
void logout()
{
cout<<"\nEnter Break....";
getch();
}
void menu(int a[],int n)
{
int chon;
cout<<"\n1.Exchage Sort\n";
cout<<"2.Selection Sort\n";
cout<<"3.Boble Sort\n";
cout<<"4.Insertion Sort\n";
cout<<"5.Exit\n";
cout<<"#Lua chon: ";
cin>>chon;
switch(chon)
{
case 1:
input(a,n);
exchage_sort(a,n);
logout();
break;
case 2:
input(a,n);
selection_sort(a,n);
logout();
break;
case 4:
input(a,n);
insertion_sort(a,n);
logout();
break;
case 3:
input(a,n);
boble_sort(a,n);
logout();
break;
case 5:
exit(0);
default:
cout<<"Khong co";
}
}
int main()
{
int *a=NULL;
int n;
while(true)
{
system("cls");
banner();
menu(a,n);
}
delete[] a; //giai phong bo nho da cap phat
cout<<"\n\n";
}
