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


Giải thuật: Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau: Input: f0 là tập tin cần sắp thứ tự. Output: f0 là tập tin đã được sắp thứ tự. Gọi f1, f2 là 2 tập tin trộn. Các tập tin f0, f1, f2 có thể là các tập tin tuần tự (text file) hay có thể là các tập tin nhị phân.

 Bước 1:
 - Giả sử các phần tử trên f0 là:  24 12 67 33 58 42 11 34 29 31
 - Khởi tạo f1, f2 rỗng
 - Thực hiện phân bố m=1 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 24 67 58 11 29 f2: 12 33 42 34 31
 Trộn f1, f2 thành f0:
 f0: 12 24 33 67 42 58 11 34 29 31

 Bước 2:
 -Phân bố m=2 phần tử lần lượt từ f0 vào f1 và f2:
 f1: 12 24 42 58 29 31
f0: 12 24 33 67 42 58 11 34 29 31
f2: 33 67 11 34
- Trộn f1, f2 thành f0: f1: 12 24 42 58 29 31 f0: 12 24 33 67 11 34 42 58 29 31 f2: 33 67 11 34

Bước 3: - Tương tự bước 2, phân bố m=4 phần tử lần lượt từ f0 vào f1 và f2, kết quả thu được như sau: f1: 12 24 33 67 29 31 f2: 11 34 42 58 - Trộn f1, f2 thành f0: f0: 11 12 24 33 34 42 58 67 29 31

Bước 4: - Phân bố m=8 phần tử lần lượt từ f0 vào f1 và  f2: f1: 11 12 24 33 34 42 58 67 f2: 29 31 - Trộn f1, f2 thành f0: f0: 11 12 24 29 31 33 34 42 58 67

Bước 5: Lặp lại tương tự các bước trên, cho đến khi chiều dài m của run cần phân bổ lớn hơn chiều dài n của f0 thì dừng.

void chia(FILE *a,FILE *b,FILE *c,int p) void main (void) { FILE *a,*b,*c; tao_file(); xuat_file(); p = 1; while (p < n) { chia(a,b,c,p); tron(b,c,a,p); p=2*p; } }

void chia(FILE *a,FILE *b,FILE *c,int p) while (!feof(a)) { /*Chia p phan tu cho b*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(b,"%3d",x); dem++; }

 dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }
 void tron(FILE *b,FILE *c,FILE *a,int p) int stop,x,y,l,r; a=fopen("d:\ctdl\sortfile\bang.int","wb"); b=fopen("d:\ctdl\sortfile\bang1.int","rb"); c=fopen("d:\ctdl\sortfile\bang2.int","rb"); while ((!feof(b)) && (!feof(c))) { l=0;/*so phan tu cua b da ghi len a*/ r=0;/*so phan tu cua c da ghi len a*/ fscanf(b,"%3d",&x); fscanf(c,"%3d",&y); stop=0;

while ((l!=p) && (r!=p) && (!stop)) { if (x<y) { fprintf(a,"%3d",x); l++; if ((l<p) && (!feof(b))) /*chua du p phan tu va chua het file b*/ fscanf(b,"%3d",&x); else { fprintf(a,"%3d",y); r++; if (feof(b)) stop=1; } }

else
{
fprintf(a,"%3d",y); r++; if ((r<p) && (!feof(c))) /*chua du p phan tu va chua het file c*/ fscanf(c,"%3d",&y); else {

fprintf(a,"%3d",x); l++; if (feof(c)) stop=1; } } } //Chep phan con lai cua p phan tu tren b len a
while ((!feof(b)) && (l<p)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); l++; }

//Chep phan con lai cua p phan tu tren c len a while ((!feof(c)) && (r<p)) { fscanf(c,"%3d",&y); fprintf(a,"%3d",y); r++; } } if (!feof(b)) { /*chep phan con lai cua b len a*/ while (!feof(b)) { fscanf(b,"%3d",&x); fprintf(a,"%3d",x); } }

{
fscanf(c,"%3d",&x); fprintf(a,"%3d",x);
} } fclose(a);  fclose(b);  fclose(c); }

 /*Chia p phan tu cho c*/ dem=0; while ((dem<p) && (!feof(a))) { fscanf(a,"%3d",&x); fprintf(c,"%3d",x); dem++; } }

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ố.
Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, … tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, ….

Bước 1 :// k cho biết chữ số dùng để phân loại hiện hành
k = 0; // k = 0: hàng đơn vị; k = 1: hàng chục; …
Bước 2 : //Tạo các lô chứa các loại phần tử khác nhau
Khởi tạo 10 lô B0, B1, …, B9 rỗng;
Bước 3 :
For i = 1 .. n do
Đặt ai vào lô Bt với t: chữ số thứ k của ai;
Bước 4 :
Nối B0, B1, …, B9 lại (theo đúng trình tự) thành a.
Bước 5 :
k = k+1;Nếu k < m thì trở lại bước 2. Ngược lại: Dừng

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 :
Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.
Bước 4 :
k = k*2;
Nếu k < n thì trở lại bước 2.
Ngược lại: Dừng
Dữ liệu hỗ trợ: 2 mảng b, c:
int  b[MAX], c[MAX], nb, nc;
Các hàm cần cài đặt:
void MergeSort(int a[], int N); : Sắp xếp mảng (a, N) tăng dần
void Distribute(int a[], int N, int &nb, int &nc, int k); Phân phối đều luân phiên các dãy con độ dài k từ mảng a vào hai mảng con b và c
void Merge(int a[], int nb, int nc, int k); : Trộn mảng b và mảng c vào mảng a
void MergeSubarr(int a[], int nb, int nc, int &pa, int &pb, int &pc, int k); : Trộn một cặp dãy con từ b và c vào a


int b[MAX], c[MAX], nb, nc;

void MergeSort(int a[], int N)
{
int k;
for (k = 1; k < N; k *= 2) 
{
Distribute(a, N, nb, nc, k);
Merge(a, nb, nc, k);
}
}
void Distribute(int a[], int N, int &nb, int &nc, int k)
{
int i, pa, pb, pc;
pa = pb = pc = 0;
while (pa < N)
{
for (i=0; (pa<N) && (i<k); i++, pa++, pb++)
b[pb] = a[pa];
for (i=0; (pa<N) && (i<k); i++, pa++, pc++)
c[pc] = a[pa];
}
nb = pb; nc = pc;
}
void Merge(int a[],int nb, int nc,int k)
{ int p, pb, pc, ib, ic, kb, kc;
p=pb=pc=0; ib=ic=0;
while((nb>0)&&(nc>0))
{ kb=min(k,nb); kc=min(k,nc);
if(b[pb+ib]<=c[pc+ic])
{ a[p++]=b[pb+ib]; ib++;
if(ib==kb)
{ 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]; ic++;
if(ic==kc)
{
for(;ib<kb;ib++) a[p++]=b[pb+ib];
pb+=kb;  pc+=kc; ib = ic=0;
nb-=kb; nc-=kc;
}
}
}
}
int min(int a,int b)
{
if(a>b) return b;
else return a;
}

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

Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3 chỉ có 1 phần tử  : đã có thứ tự
 khi đó dãy con ban đầu đã được sắp.
Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3  có nhiều hơn 1 phần tử  thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp.
Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …
Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử
Kết thúc; //dãy đã được sắp xếp
Bước 2: Phân hoạch dãy aleft … aright thành các đoạn: aleft.. aj, aj+1.. ai-1, ai.. aright
Đoạn 1  x
Đoạn 2: aj+1.. ai-1  = x
Đoạn 3: ai.. aright   x
Bước 3: Sắp xếp đoạn 1: aleft.. aj
Bước 4: Sắp xếp đoạn 3: ai.. aright


Bước 1 : Chọn tùy ý một phần tử  a[k] trong dãy là giá trị mốc ( l ≤ k ≤ r):  
x = a[k];   i = l;  j = r;
Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử
a[i], a[j] nằm sai chỗ :
Bước 2a : Trong khi (a[i]<x) i++;
Bước 2b : Trong khi (a[j]>x) j--;
Bước 2c : Nếu  i< j Swap(a[i],a[j]);
Bước 3 : Nếu  i < j: Lặp lại Bước 2.   Ngược lại: Dừng

void QuickSort(int 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)
{ 
Swap(a[i],a[j]);
        i++ ; j--;
}
} while(i <= j);

if(left<j)
QuickSort(a, left, j);
if(i<right)
QuickSort(a, i, right);
}

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)
Giai đoạn 1 : Hiệu chỉnh dãy số ban đầu thành heap
Giai đoạn 2:  Sắp xếp dãy số dựa trên heap:
Bước 1:Đưa phần tử  lớn  nhất về vị trí đúng ở cuối dãy:             r = n-1;  Swap (a1 , ar );
Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r-1;        Hiệu chỉnh phần còn lại của dãy từ  a1 , a2 ... ar thành một heap.
Bước 3:
       Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2   Ngược lại : Dừng
Heap: Là một dãy các phần tử  al, al+1 ,... , ar  thoả các quan hệ với mọi i  [l, r]:
ai  a2i+1
ai  a2i+2 // (ai , a2i+1), (ai , a2i+2 ) là các cặp phần tử liên đới
Cho dãy số  : 12   2   8   5  1   6   4  15
Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành Heap
Giai đoạn 2: Sắp xếp dãy số dựa trên Heap

void shift(int a[],int l,int r)
{
int x,i,j;
i=l;
j=2*i+1;
x=a[i];
while(j<=r)
{ if(j<r)
if(a[j]<a[j+1]) //tim phan tu lon nhat a[j] va a[j+1]

j++; //luu chi so cua phan tu nho nhat trong hai phan tu 
if(a[j]<=x) return;
else
{ a[i]=a[j];
a[j]=x;
i=j;
j=2*i+1;
x=a[i];
}
}
}
void CreateHeap(int a[],int n)
{ int l;
l=n/2-1;
while(l>=0)
{
shift(a,l,n-1);
l=l-1;
}
}
void HeapSort(int a[],int n)
{ int r;
CreateHeap(a,n);
r=n-1;
while(r>0)
{
Swap(a[0],a[r]);//a[0] la nút gốc
r--;
if(r>0)
shift(a,0,r);
}
}

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 ...
....
Dãy con thứ  h     : ah a2h a3h ...
Tiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử  được đưa về vị trí đúng tương đối
Giảm khoảng cách h để tạo thành các dãy con mới
Dừng khi h=1
Giả sử quyết định sắp xếp k bước, các khoảng cách  chọn phải thỏa điều kiện :
hi  > hi+1  và hk = 1
 hi  = (hi-1  - 1)/3 và hk = 1, k = log3n-1
Ví dụ :127, 40, 13, 4, 1
 hi  = (hi-1 - 1)/2 và hk = 1, k = log2n-1
Ví dụ : 15, 7, 3, 1
h có dạng 3i+1: 364, 121, 40, 13, 4, 1
Dãy fibonaci: 34, 21, 13, 8, 5, 3, 2, 1
h là dãy các số nguyên tố giảm dần đến 1: 13, 11, 7, 5, 3, 1.
Bước 1: Chọn k khoảng cách h[1], h[2], ..., h[k];
i = 1;
Bước 2: Phân chia dãy ban đầu thành các dãy con   cách nhau h[i] khoảng cách.
Sắp xếp từng dãy con bằng phương pháp   chèn trực tiếp;
Bước 3 : i = i+1;            Nếu  i > k : Dừng            Ngược lại : Lặp lại Bước 2.    
Cho dãy số a:
12   2 8 5 1 6 4 15

Giả sử chọn các khoảng cách là 5, 3, 1

void ShellSort(int a[],int n, int h[], int k)
{ int step,i,j, x,len;
for (step = 0 ; step <k; step++)
{ len = h[step];
for (i = len; i<n; i++)
{
x = a[i]; 
j = i-len; // a[j] đứng kề trước a[i] trong cùng dãy con 
while ((x<a[j])&&(j>=0)// sắp xếp dãy con chứa  x 
{ // bằng phương pháp chèn trực tiếp 
a[j+len]  = a[j];
j = j - len;
}
a[j+len] = x;
}
}
}

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 }
}

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
}
}

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

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];
}

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];
}

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];
}

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];
}