Life would be so much simple if we don't care so much


Cài đặt các thuật toán sắp xếp trên C++

Đăng ngày: 21:02 09-12-2008

Bài viết này mình đã đăng cách đây cũg khá lâu trên PLus, mang sang đây cho phong phú 😀

(Download project tai đây Project Sort)
Đây là các bài tập C++, theo mình nghĩ 1 số bạn học C/C++ cũng rất quan tâm, bổ trợ cho việc thao tác cài đặt các hàm trên C++:
(Bạn nào thấy nên sửa lại chỗ nào thì để lại comment nha)

Cài đặt các thuật toán sắp xếp trên C++:

Bài làm tổ chức ct theo 2 tập tin: Ham chuc nang.h và Ham main.ccp
//Ham chuc nang.h

#include
#include
#include
#include
using namespace std;
#define MAX 10000

typedef int Array[MAX];
typedef char *String;

//Khai bao cac ham bo tro
void Nhap(Array a, int n);
void Xuat(Array a, int n);
void Gan(Array a,Array b,int n);
void Hoanvi(int &a, int &b);
int Min(int a, int b);
void Thucthi(String TenHam,Array a, int n,void (*HamSapXep)(Array, int));

//Khai bao nguyen mau cac ham sap xep
void Selection_sort(Array a, int n);
void Insertion_sort(Array a, int n);
void Interchange_sort(Array a, int n);
void Bubble_sort(Array a, int n);
void Shell_sort(Array a, int n);
void Taobuocnhay(int h[MAX],int n,int &k);
void Phanhoach(Array a,int left, int right);
void Quick_sort(Array a,int n);
void Shaker_sort(Array a, int n);
//Merge_sort
void Merge_sort(Array a, int n);
void Merge(Array a, int n,int k, int nb, int nc, Array b, Array c);
//Heap_sort
void Shift(Array a,int left, int right);
void CreateHeap(Array a, int n);
void Heap_sort(Array a, int n);
//Radix_sort
void Radix_sort(Array a, int n);
int FindMax(Array a, int n);
int CountDigits(int number);

//*___________________CAC HAM BO TRO__________________________

void Nhap(Array a, int n)
{
int i;
for(i=0;i<n;i++)
a[i]=rand()%100;
}

void Xuat(Array a, int n)
{
for(int i=0;i<n;i++)
cout< <<“\t”;
}

void Gan(Array a,Array b,int n)
{
for(int i=0;i<n;i++)
b[i]=a[i];
}

void Hoanvi(int &a, int &b)
{
int Tam;
Tam=a;
a=b;
b=Tam;
}

int Min(int a, int b)
{
int Min;
Min=a;
if(b<a)
Min=b;
return Min;
}

//Ham dung 1 con tro dong thoi tinh tg ham sx (dung con tro ham)
void Thucthi(String TenHam,Array a, int n,void (*HamSapXep)(Array, int))
{
time_t start, stop;
Array b;
cout<<“\nDang thuc thi ham sap xep chon…:”;
cout<<“\n”;
Gan(a,b,n);//Gan mang a cho b
start=time(NULL);//Thoi gian bat dau sx
(*HamSapXep)(b,n);//Goi ham sx cua con tro ham
stop=time(NULL);//Thoi gian ket thuc sx
cout<<“\nKet qua ham sap xep:”<
cout<<“\n”;
Xuat(b,n);
cout<<“\n”;
cout<<“\nThoi gian bat dau thuc hien: “<
cout<<“\nThoi gian ket thuc thuc hien: “<
cout<<“\nThoi gian thuc hien cua ham: “< <<“\n”;
}

//_________________CAC HAM SAP XEP____________________________

//1> Phuong phap chon truc tiep_________
void Selection_sort(Array a,int n)
{
int i,j,Csmin;
for(i=0;i<n-1;i++)
{
Csmin=i;
for(j=i+1;j++)
{
if(a[j]<a[Csmin])
Csmin=j;
}
Hoanvi(a[Csmin],a[i]);
}
}

//2> Phuong phap chen truc tiep_________
void Insertion_sort(Array a, int n)
{
int i,x,pos;
for(i=1;i<n;i++)
{
x=a[i];//Luu gia tri a[i] lai tren x
pos=i-1;
while(pos>=0&&a[pos]>x)
{
a[pos+1]=a[pos];//doi cho cac phan tu se dung sau x
pos–;
}
a[pos+1]=x;//chen x vao day
}
}

//3> Phuong phap doi cho truc tiep______
void Interchange_sort(Array a, int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[j]<a[i])
Hoanvi(a[i],a[j]);
}

//4> Phuong phap bubble sort_____________
void Bubble_sort(Array a, int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=n-1;j>1;j–)
if(a[j]<a[i])
Hoanvi(a[i],a[j]);
}
//5> Phuong phap heap sort________________
void Shift(Array a,int left, int right)
{
int p;
p=2*left;
if(p>right)
return;
if(p<right)
{
if(a[p]<a[p+1])
p=p+1;
}
if(a[left]<a[p])
{
Hoanvi(a[left],a[p]);
Shift(a,p,right);
}
return;
}
void CreateHeap(Array a, int n)
{
int i;
int left;
left=(n-1)/2;
int j=(n+1)/2-1;
for(i=j;0<=i;i–)
Shift(a,i,n-1);
}
void Heap_sort(Array a, int n)
{
int right=n-1;
CreateHeap(a,n);
for(int i=n-1;0
{
Hoanvi(a[0],a[i]);
Shift(a,0,i-1);
}
}

//6> Phuong phap shell sort_____________
void

Shell_sort(Array a, int n) {
Array h;
int k = (log(double (n)))/(log(2.0)) – 1;
h[k] = 1;

for(int i = k-1; i >= 0; i–)
h[i] = h[i+1] * 2 + 1;

for(int step = 0; step <= k; step++)
{
int len = h[step];
for(int i = len; i < n; i++)
{
int j = i – len;
int x = a[i];
while(a[j] > x && j >= 0)
{
a[j+len] = a[j];

j = j – len;
}
a[j+len] = x;
}
}
}

//7> Phuong phap Quick_sort_____________
void Phanhoach(Array a,int left, int right)
{
int i,j,x;
x=a[(left+right)/2];
i=left;
j=right;
do
{
while(a[i]<x)
i++;
while(a[j]>x)
j–;
if(i<=j)
{
Hoanvi(a[i],a[j]);
i++;
j–;
}
}
while(i<j);
if(left<j)
Phanhoach(a,left,j);
if(i<right)
Phanhoach(a,i,right);
}
void Quick_sort(Array a,int n)
{
Phanhoach(a,0,n-1);
}

//8> Phuong phap Shaker_sort____________
void Shaker_sort(Array a, int n)
{
int i, j, left, right, k;
left=0;
right=n-1;
k=n-1;
while(left<right)
{
for(i=right;i>left;i–)
{
if(a[i]<a[i-1])
{
Hoanvi(a[i],a[i-1]);
k=i;
}
}
left=k;
for(j=left;j<right;j++)
{
if(a[j]>a[j+1])
{
Hoanvi(a[j],a[j+1]);
k=j;
}
}
right=k;
}
}

//9> Phuong phap Merge sort___________
void Merge_sort(Array a, int n)
{
Array b,c;
int p,pb,pc;//Cac chi so tren mang a,b,c
int i;
int k=1;
do//Do dai cua day con khi phan hoach
{
p=pb=pc=0;
while(p<n)//Gan gia tri cua a xen ke k so  vao b va c
{
for(i=0;(p<n)&&(i<k);i++)
b[pb++]=a[p++];
for(i=0;(p<n)&&(i<k);i++)
c[pc++]=a[p++];
}
Merge(a,n,k,pb,pc,b,c);
k*=2;
}
while(k<n);

}
void Merge(Array a, int n,int k, int nb, int nc, Array b, Array c)
{
int p,pb,pc,ib,ic,kb,kc;
p=pb=pc=0;
ib=ic=0;
while((0<nb)&&(0<nc))
{
kb=Min(k,nb);
kc=Min(k,nc);
if(b[pb+ib]<=c[pc+ic])//So sanh 2 so dau day cua b, c
{
a[p++]=b[pb+ib];//Gan gia tri cua b vao a
ib++;//tang len toi khi bang kb
if(ib==kb)//Xem ke (k so) gan gia tri cua c vao a
{
for(;ic<kc;ic++)
a[p++]=c[pc+ic];
pb+=kb;
pc+=kc;
ib=ic=0;
nb-=kb;
nc-=kc;
}
}
else
{
a[p++]=c[pc+ic];//Gan gia tri cua c vao a
ic++;
if(ic==kc)
{
for(;;ib<kb;ib++)
a[p++]=b[pb+ib];
pb+=kb;
pc+=kc;
ib=ic=0;
nb-=kb;
nc-=kc;
}
}
}
}
//10> Phuong phap Radix sort___________
void Radix_sort(Array a, int n)
{
int max = a[FindMax(a, n)];
int k = CountDigits(max);
int b = 1, tam, dem;

int Lo[10][MAX];
int count[10];

for (dem = 0; dem<10; dem++)
count[dem] = 0;

for (int step = 0; step <= k; step++)
{
for (int i=0; i<n; i++)
{
tam = (a[i] / b) % 10;
Lo[tam][count[tam]] = a[i];
count[tam]++;
}

int i = 0;

for (dem = 0; dem < 10; dem++)
if (count[dem] > 0)
{
for (int c = 0; c < count[dem]; c++)
{
a[i] = Lo[dem][c];
Lo[dem][c] = 0;
i++;
}
count[dem] = 0;
}
b *= 10;
}
}
int FindMax(Array a, int n)
{
int Cs_max = 0;

for (int i=1; i<n; i++)
if (a[Cs_max] < a[i])
Cs_max = i;

return Cs_max;
}
int CountDigits(int number)
{
int count = 0;
while (number > 0)
{
number = number / 10;
count ++;
}
return count;
}

Ham main.ccp

#include
#include
//Cac ham menu
void Menu();
int Chon_Menu();
void Xuly_Menu(Array a, int n, int chon);

void main()
{
int n,chon;
Array a;
cout<<“Nhap so phan tu cua mang: “;
cin>>n;
Nhap(a,n);
Xuat(a,n);
Menu();
do
{
chon = Chon_Menu();
Xuly_Menu(a,n,chon);
}
while(1);
}

void Menu()
{
cout<<“\n_______________BANG MENU________________”;
cout<<“\n__1> Phuong phap chon truc tiep_________”;
cout<<“\n__2> Phuong phap chen truc tiep_________”;
cout<<“\n__3> Phuong phap doi cho truc tiep______”;
cout<<“\n__4> Phuong phap noi bot________________”;
cout<<“\n__5> Phuong phap Heap sort______________”;
cout<<“\n__6> Phuong phap Shell sort_____________”;
cout<<“\n__7> Phuong phap Quick sort_____________”;
cout<<“\n__8> Phuong phap Shaker sort____________”;
cout<<“\n__9> Phuong phap Merge sort_____________”;
cout<<“\n_10> Phuong phap Radix sort_____________”;
cout<<“\n_11> Thoat khoi chuong trinh____________”;
}
int Chon_Menu()
{
int Chon;
for(;;)
{
cout<<“\nNhap chon tu 1–>11: “;
cin>>Chon;
if(1<=Chon&&Chon<=11)
break;
}
return Chon;
}
void Xuly_Menu(Array a, int n, int chon)
{
int left=0;
int right=n-1;
switch(chon)
{
case 1:
cout<<“\n__1> Phuong phap chon truc tiep_________”;
cout<<“\n”;
Thucthi(“PP Chon truc tiep”,a,n,Selection_sort);
break;
case 2:
cout<<“\n__2> Phuong phap chen truc tiep_________”;
cout<<“\n”;
Thucthi(“PP Chon truc tiep”,a,n,Insertion_sort);
break;
case 3:
cout<<“\n__3> Phuong phap doi cho truc tiep______”;
cout<<“\n”;
Thucthi(“PP doi cho truc tiep”,a,n,Interchange_sort);
break;
case 4:
cout<<“\n__4> Phuong phap Bubble sort____________”;
cout<<“\n”;
Thucthi(“PP Bubble sort”,a,n,Bubble_sort);
break;
case 5:
cout<<“\n__5> Phuong phap Heap sort______________”;
cout<<“\n”;
Thucthi(“PP Heap sort”,a,n,Heap_sort);
break;
case 6:
cout<<“\n__6> Phuong phap Shell sort_____________”;
cout<<“\n”;
Thucthi(“PP shell sort”,a,n,Shell_sort);
break;
case 7:
cout<<“\n__7> Phuong phap Quick sort_____________”;
cout<<“\n”;
Thucthi(“PP quick sort”,a,n,Quick_sort);
break;
case 8:
cout<<“\n__8> Phuong phap Shaker sort____________”;
cout<<“\n”;
Thucthi(“PP shaker sort”,a,n,Shaker_sort);
break;
case 9:
cout<<“\n__9> Phuong phap Merge sort_____________”;
cout<<“\n”;
Thucthi(“PP merge sort”,a,n,Merge_sort);
break;
case 10:
cout<<“\n_10> Phuong phap Radix sort_____________”;
cout<<“\n”;
Thucthi(“PP radix sort”,a,n,Radix_sort);
break;
case 11:
cout<<“\n_11> Thoat khoi chuong trinh____________”;
exit(1);
}
}

Nếu blog ko hiển thị đủ code thì mọi ng` down project này về nha!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: