sắp xếp trộn run sắp xếp ngoại

 Phương pháp trộn Run
Khái niệm cơ bản:
 Run là một dãy liên tiếp các phần tử được sắp thứ tự. Ví dụ 2  4  7  12  50 là một run gồm có 5 phần tử
 Chiều dài run chính là số phần tử trong Run. Chẳng hạn, run trong ví dụ trên có chiều dài là 5.
 7 8 5 3 9 12 4 23 78 90 45 54

Read More

thuật toán sắp xếp radix sort

Radix Sort là một thuật toán tiếp cận theo một hướng hoàn toàn khác.
Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix Sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó Radix Sort còn có tên là Postman’s Sort.
Radix Sort không hề quan tâm đến việc so sánh giá trị của phần tử mà bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.
Mô phỏng lại qui trình trên, để sắp xếp dãy a1, a2, ..., an, giải thuật Radix Sort thực hiện như sau:
Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a1, a2, ..., an là một số nguyên có tối đa m chữ số.

Read More

thuật toán merge sort - sắp xếp trộn

Giải thuật Merge sort sắp xếp dãy a1, a2, ..., an dựa trên nhận xét sau:
Mỗi dãy a1, a2, ..., an bất kỳ là một tập hợp các dãy con liên tiếp mà mỗi dãy con đều đã có thứ tự.
Ví dụ: dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 dãy con không giảm (12); (2, 8); (5); (1, 6); (4, 15).
Dãy đã có thứ tự coi như có 1 dãy con.
Hướng tiếp cận: tìm cách làm giảm số dãy con không giảm của dãy ban đầu.
Bước 1 : // Chuẩn bị
k = 1; // k là chiều dài của dãy con trong bước hiện hành
Bước 2 :
Tách dãy a0, a1, ., an-1 thành 2 dãy b, c theo nguyên tắc luân phiên từng nhóm k phần tử:
b = a0, ., ak, a2k, ., a3k, .
c = ak+1, ., a2k+1, a3k+1, .
Bước 3 :

Read More

thuật toán quick sort - sắp xếp nhanh

Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần :

Phần 1: Gồm các phần tử  có giá trị bé hơn x
Phần 2: Gồm các phần tử  có giá trị bằng  x
Phần 3: Gồm các phần tử  có giá trị lớn hơn x
với x là giá trị của một phần tử  tùy ý trong dãy ban đầu.
Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn:
1. ak  ≤ x , với k = 1 .. j
2. ak  = x , với k =  j+1 .. i-1
3. ak   x , với k =  i..N

Read More

thuật toán heap sort - sắp xếp vun đống, (cây)

thuật toán heap sort - sắp xếp vun đống, (cây)

Heap Sort tận dụng được các phép so sánh ở bước i-1 mà thuật toán sắp xếp chọn trực tiếp không tận dụng được
Để làm được điều này Heap sort thao tác dựa trên cây.
Ở cây trên, phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i +1, do đó phần tử ở nút gốc là phần tử lớn nhất.
Nếu loại bỏ gốc ra khỏi cây, thì việc cập  nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác thì bảo toàn.
Bước kế tiếp có thể sử dụng lại kết quả so sánh của bước hiện tại.
Vì thế độ phức tạp của thuật toán O(nlog2n)

Read More

thuật toán shell sort - cải tiến của chèn trực tiếp

thuật toán shell sort - cải tiến của chèn trực tiếp

shell sort là Cải tiến của phương pháp chèn trực tiếp
Ý tưởng:
Phân hoạch dãy thành các dãy con
Sắp xếp các dãy con theo phương pháp chèn trực tiếp
Dùng phương pháp chèn trực tiếp sắp xếp lại cả dãy.
Phân chia dãy ban đầu thành những dãy con gồm các phần tử  ở cách nhau h vị trí
Dãy ban đầu : a1, a2, ..., an được xem như sự xen kẽ của các dãy con sau :
Dãy con thứ nhất : a1 ah+1 a2h+1 ...
Dãy con thứ  hai  : a2 ah+2 a2h+2 ...
....

Read More

thuật toán binary insertion sort - chèn nhị phân

thuật toán binary insertion sort - chèn nhị phân

void BInsertionSort(int a[],int n )
{
int l,r,m,i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<n ; i++)
{
x = a[i]; l = 0;
r = i-1;
while(l<=r) // tìm vị trí chèn x
{
m = (l+r)/2;
// tìm vị trí thích hợp m
if(x < a[m]) r = m-1;
else l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j];// dời các phần tử sẽ đứng sau x
a[l] = x; // chèn x vào dãy }
}

Read More

thuật toán insertion sort - chèn trực tiếp

thuật toán insertion sort - chèn trực tiếp

Giả sử có một dãy a0 , a1 ,... ,an-1 trong đó i phần tử đầu tiên a0 , a1 ,... ,ai-1 đã có thứ tự.
Tìm cách chèn phần tử  ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a0 , a1,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i).

Bước 1:  i = 1; //giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào
Bước 3: Dời chỗ các phần tử  từ a[pos] đến a[i-1]   sang phải 1 vị trí để dành chổ cho a[i]
Bước 4: a[pos] = x; //có đoạn a[1]..a[i]  đã được sắp
Bước 5: i = i+1;
Nếu  i < n : Lặp lại Bước 2
Ngược lại  : Dừng

void InsertionSort(int d, int n 
{ int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(i=1 ; i<n ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x; // chèn x vào dãy
}
}

Read More

sắp xếp từ điển trong lập trình C++ - bài tập đồ án CTDL & GT

sắp xếp từ điển trong lạp trình C++ - bài tập đồ án CTDL & GT

sắp xếp từ điển trong lập trình c/c++,tạo 1 mảng 1 chiều chứa các từ tiếng anh lấy từ file http://blackberryvietnam.net/threads/du-lieu-tu-dien-cho-ung-dung-ddict.897/ . sau đó dùng các thuật toán sắp xếp để sắp xếp mảng trên theo thứ tự và so sánh thời gian thực hiện các thuật toán.
lưu ý:để thuận tiện việc thao tác, chỉ lấy các từ đơn dưới 15 kí tự, các từ tiếng anh được tách ra từ dữ liệu từ điển việt-anh. (không phải từ điển anh-việt).
trong code dưới đây, dữ liệu nguồn là file va.dd, danh sách các từ tiếng anh lọc ra được và sắp xếp được đưa vào file av.dd.
*đây là bài tập đồ án của thầy Toàn UIT, dưới đây chỉ là các code sắp xếp, phần main() thì các bạn chỉnh sửa lại cho phù hợp với yêu cầu của đồ án, phần main() là ý kiến sáng tạo để hoàn thành bài tập, tôi chỉ viết đơn giản như vậy để chạy thử xem code sắp xếp có chạy đúng hay không thôi.

#include<iostream>
#include<time.h>
using namespace std;

void bang(char *a,char *b);
void doi(char *a,char *b);

//các thuật toán sắp xếp
void interchange(char s[][15],int k);
void select(char s[][15],int n);
void bubble(char s[][15],int n);
void insert(char s[][15],int n);
void insertbinary(char s3[][15],int k);
void shacker(char s[][15],int n);
void shell(char s[][15],int n);
void quick(char s[][15],int l,int r);
void heap(char s[][15],int n);
void merge(char a[][15],int n);

void main()
{
//lấy các từ tiếng anh đưa vào chuỗi s3
FILE *t,*t1;
char s[300];
char *s1,*s2,s3[50000][15];
t = fopen("E:\\va.dd","r");
t1=fopen("E:\\av.dd","w+");
while(fgets(s,300,t)!=NULL)
{
s1=strstr(s,"##");
if(s1!=NULL)
{
s2=strstr(s1,"|-");
if(s2!=NULL && strlen(s2)<15) fputs(s2+2,t1);
}
}
rewind(t1);
int k=0;
while(fgets(s,15,t1)!=NULL)
{
strcpy(s3[k],s);
k++;
}
int n=k;  
//sắp xếp
cout<<"\ndang sap xep...";
double tg;
double a=clock();
shell(s3,k);//kiểu sắp xếp. thay bằng các kiểu sắp xếp khác nhau để so sanh thời gian
//đang dùng shell sort..
double b=clock();
cout<<"\nda xep xong!\nthoi gian sap xep la: "<<(b-a)/1000<<" giay.";

rewind(t1);
for(int i=0;i<k;i++) fputs(s3[i],t1);
fcloseall();
system("pause"); 
}
void chinh(char s[][15],int l,int r)
{
int j=2*l+1;
while(j<=r)
{
if(j<r && stricmp(s[j],s[j+1])<0) j++;
if(stricmp(s[l],s[j])>=0) return;
else
{
doi(s[l],s[j]);
l=j;
j=2*l+1;
}
}
}
void taoheap(char s[][15],int n)
{
int l=n/2-1;
while(l>=0)
{
chinh(s,l,n-1);
l--;
}
}
void heap(char s[][15],int n)
{
int r=n-1;
taoheap(s,n);
while(r>0)
{
doi(s[0],s[r]);
r--;
if(r>0) chinh(s,0,r);
}
}
void quick(char s[][15],int l,int r)
{
int i=l,j=r,m=(l+r)/2;
while(i<=j)
{
while(stricmp(s[i],s[m])<0) i++;
while(stricmp(s[j],s[m])>0) j--;
if(i<=j)
{
doi(s[i],s[j]);
i++;j--;
}
}
if(i<r) quick(s,i,r);
if(j>l) quick(s,l,j);
}
void shacker(char s[][15],int n)
{
int l=0,r=n-1,k=n-1,i;
while(l<r)
{
for(i=r;i>l;i--)
if(stricmp(s[i],s[i-1])<0){ doi(s[i],s[i-1]);k=i;}
l=k;
for(i=l;i<r;i++)
if(stricmp(s[i],s[i+1])>0){doi(s[i],s[i+1]);k=i;}
r=k;
}
}
void bubble(char s[][15],int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(stricmp(s[j],s[j-1])<0) doi(s[j],s[j-1]);
}
void insert(char s[][15],int n)
{
for(int i=1;i<n;i++)
{
char x[15];
bang(x,s[i]);
int j=i-1;
while(stricmp(s[j],x)>0 && j>=0)
{
bang(s[j+1],s[j]);
j--;
}
bang(s[j+1],x);
}
}
void interchange(char s[][15],int k)
{
for(int i=0;i<k-1;i++)
for(int j=i+1;j<k;j++)
if(stricmp(s[i],s[j])>0) doi(s[i],s[j]);
}
void select(char s[][15],int n)
{
int dem=0;
for(int i=0;i<n-1;i++)
{
int m=i;
for(int j=i+1;j<n;j++)
if(stricmp(s[m],s[j])>0) m=j;
doi(s[i],s[m]);
}
}
void shell(char s[][15],int n)
{
int h[10]={10129,1678,437,256,134,62,5,3,2,1},k=10;
int i,j,len,step;
char x[15];
for(step=0;step<k;step++)
{
len=h[step];
for(i=len;i<n;i++)
{
bang(x,s[i]);
j=i-len;
while(j>=0 && stricmp(s[j],x)>0)
{
bang(s[j+len],s[j]);
j=j-len;
}
bang(s[j+len],x);
}
}
}
void insertbinary(char s3[][15],int k)
{
//sắp xếp chèn nhị phân
int l,r,m,i,j,dem=0;
char x[15];
for(i=1;i<k;i++)
{
l=0;r=i-1;
for(j=0;j<strlen(s3[i]);j++) x[j]=s3[i][j];x[j]='\0';
while(l<=r)
{
m=(l+r)/2;
if(stricmp(x,s3[m])<0) r=m-1;
else l=m+1;
}
for(j=i;j>l;j--) bang(s3[j],s3[j-1]);
bang(s3[l],x);
}
}
void bang(char *a,char *b)//phép gán
{
int i;
for(i=0;i<strlen(b);i++) a[i]=b[i];
a[i]='\0';
}
void doi(char *a,char *b)//hoán đổi vị trí
{
int i;
char c[300];
for(i=0;i<strlen(a);i++) c[i]=a[i];c[i]='\0';
for(i=0;i<strlen(b);i++) a[i]=b[i];a[i]='\0';
for(i=0;i<strlen(c);i++) b[i]=c[i];b[i]='\0';

}
void phanphoi(char a[][15],int n,char b[][15],int &nb,char c[][15],int &nc,int k)
{
int pa,pb,pc,i;
pa=pb=pc=0;
while(pa<n)
{
i=0;
while(i<k && pa<n)
{
bang(b[pb++],a[pa++]);
i++;
}
i=0;
while(i<k && pa<n)
{
bang(c[pc++],a[pa++]);
i++;
}
}
nb=pb;nc=pc;
}
int min(int a,int b)
{
if(a<b) return a;
return b;
}
void tron(char a[][15],int n,char b[][15],int nb,char c[][15],int nc,int k)
{
int pa,pb,pc,kb,kc,ib,ic;
pa=pb=pc=ib=ic=0;
while(nb>0 && nc>0)
{
kb=min(k,nb);
kc=min(k,nc);
if(stricmp(b[pb+ib],c[pc+ic])<=0)
{
bang(a[pa++],b[pb+ib]);
ib++;
if(ib==kb)
{
while(ic<kc)
{
bang(a[pa++],c[pc+ic]);
ic++;
}
pb+=kb;pc+=kc;nb-=kb;nc-=kc;
ib=ic=0;
}
}
else
{
bang(a[pa++],c[pc+ic]);
ic++;
if(ic==kc)
{
while(ib<kb)
{
bang(a[pa++],b[pb+ib]);
ib++;
}
pb+=kb;pc+=kc;nb-=kb;nc-=kc;
ib=ic=0;
}
}
}
}
void merge(char a[][15],int n)
{
char (*b)[15]=new char[50000][15];
char (*c)[15]=new char[50000][15];
int nb,nc,k=1;
while(k<n)
{
phanphoi(a,n,b,nb,c,nc,k);
tron(a,n,b,nb,c,nc,k);
k*=2;
}
delete [](*b);
delete [](*c);

}


file sắp xếp từ điển

//tác giả code: Trần Khánh Toàn - ĐH CNTT

Read More

thuật toán selection sort

/*thuật toán selection sort
Ý tưởng:
Chọn phần tử nhỏ nhất trong N phần tử trong dãy hiện hành ban đầu.
Đưa phần tử này về vị trí đầu dãy hiện hành
Xem dãy hiện hành chỉ còn N-1 phần tử của dãy hiện hành ban đầu
Bắt đầu từ vị trí thứ 2;
Lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử
Bước 1:   i = 0;
Bước 2:  Tìm phần tử a[min] nhỏ nhất trong    dãy hiện hành từ a[i] đến a[N]
Bước 3 :  Đổi chỗ a[min] và a[i]
Bước 4 :  Nếu  i < N-1 thì
i = i+1; Lặp lại Bước 2;                Ngược lại: Dừng.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
int i, j, m,t;
for (i = 0; i < n - 1; i++)
{
m = i;
for (j = i + 1; j < n; j++) if (a[m]>a[j]) m = j;
t = a[i]; a[i] = a[m]; a[m] = t;
}
}
void main()
{
int a[10] = { 5, 4, 7, 8, 2, 3, 1, 9, 6, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

Read More

thuật toán interchange sort

/*thuật toán interchange sort
Ý tưởng: Xuất phát từ đầu dãy, tìm tất các các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế trong dãy.
Bước 1: i = 0;  // bắt đầu từ đầu dãy
Bước 2: j = i+1; //tìm các nghịch thế với a[i]
Bước 3:
Trong khi j < N thực hiện
Nếu a[j]<a[i] //xét cặp a[i], a[j]
Swap(a[i],a[j]);
j = j+1;
Bước 4: i = i+1;
Nếu  i < N-1: Lặp lại Bước 2.
Ngược lại:  Dừng.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
for (int i = 0; i < n - 1;i++)
for (int j = i + 1; j < n;j++)
if (a[i]>a[j])
{
a[i] += a[j]; a[j] = a[i] - a[j]; a[i] = a[i] - a[j];
}
}
void main()
{
int a[10] = { 3, 7, 4, 1, 8, 9, 2, 5, 6, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

Read More

thuật toán bubble sort

/*thuật toán bubble sort
Ý tưởng:
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i.
Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
Bước 1 : i = 0; // lần xử lý đầu tiên
Bước 2 : j = N-1;//Duyệt từ cuối dãy ngược về vị trí i
Trong khi (j > i) thực hiện:
Nếu a[j]<a[j-1]
Doicho(a[j],a[j-1]);
j = j-1;
Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu  i =N: Hết dãy. Dừng
Ngược lại : Lặp lại Bước 2.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
int i, j, t;
for (i = 0; i < n - 1;i++)
for (j = n - 1; j>i;j--)
if (a[j] < a[j - 1])
{
t = a[j]; a[j] = a[j - 1]; a[j - 1] = t;
}
}
void main()
{
int a[10] = { 3, 4, 5, 2, 8, 7, 6, 1, 9, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

Read More

thuật toán sắp xếp shaker sort

/*thuật toán sắp xếp shaker sort
Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau:
Lượt đi: đẩy phần tử nhỏ về đầu mảng.
Lượt về: đẩy phần tử lớn về cuối mảng.
Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
Bước 1: l=0; r=n-1; //Đoạn l->r là đoạn cần được sắp xếp
k=n; //ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sơ thu hẹp đoạn l->r
Bước 2:
Bước 2a:
j=r; //đẩy phần tử nhỏ về đầu mảng
Trong khi j>l
nếu a[j]<a[j-1] thì {Doicho(a[j],a[j-1]): k=j;}
j--;
l=k; //loại phần tử đã có thứ tự ở đầu dãy
Bước 2b: j=l
Trong khi j<r
nếu a[j]>a[j+1] thì {Doicho(a[j],a[j+1]); k=j;}
j++;
r=k; //loại phần tử đã có thứ tự ở cuối dãy
Bước 3: Nếu l<r lặp lại bước 2
Ngược lại: dừng

*/
#include<iostream>
using namespace std;
inline void doi(int &a, int &b)
{
int t = a; a = b; b = t;
}
void xep(int a[], int n)
{
int left = 0, right = n - 1, k,i,j;
while (left < right)
{
for (i = left; i < right; i++) if (a[i]>a[i + 1]) { doi(a[i], a[i + 1]); k = i; };
right = k;
for (j = right; j>left; j--) if (a[j] < a[j - 1]){ doi(a[j], a[j - 1]); k = j; }
left = k;
}
}
void main()
{
int a[10] = { 2, 8, 9, 5, 6, 3, 4, 7, 1, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

Read More