Thuật toán QuickSort

Thuật toán này có tên tiếng Việt là Sắp xếp nhanh

1. Ý tưởng

Thuật toán dựa trên kỹ thuật chia để trị,được đề xuất bởi C.A.R Hoare, dựa trên phép phân chia danh sách được sắp thành hai danh sách con. Khác với sắp xếp trộn, chia danh sách cần sắp xếp a[1..n] thành hai danh sách con có kích thước tương đối bằng nhau nhờ chỉ số đứng giữa danh sách, sắp xếp nhanh chia nó thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau. Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1.

2. Phần tử chốt

Kỹ thuật chọn phần tử chốt ảnh hưởng khá nhiều đến khả năng rơi vào các vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử chốt là trung vị của danh sách. Khi đó sau log2(n) lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử chốt như sau:

  • Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
  • Chọn phần tử đứng giữa danh sách làm phần tử chốt.
  • Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
  • Chọn phần tử ngẫu nhiên làm phần tử chốt. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)

3. Thuật phân chia

Sau khi phần tử chốt được chọn giải thuật phân chia nên tiến hành như thế nào?

  • Một giải pháp đơn giản nhất cho vấn đề này là duyệt từ đầu đến cuối lần lượt so sánh các phần tử của danh sách với phần tử chốt. Theo cách này, ta phải tiến hành n phép so sánh, ngoài ra còn phải dành n đơn vị bộ nhớ để lưu giữ các giá trị trung gian.
  • Một giải pháp khác được đề nghị là duyệt theo hai đường. Một đường từ đầu danh sách, một đường từ cuối danh sách. Theo cách này, ta tìm phần tử đầu tiên tính từ trái lớn hơn phần tử chốt và phần tử đầu tiên phía phải nhỏ hơn hoặc bằng phần tử chốt rồi đổi chỗ cho nhau. Tiếp tục như vậy cho đến khi hai đường gặp nhau.
  • Để có thể gọi đệ quy ta xét bài toán phân chia một danh sách con của a: a[k1,k2] thành hai danh sách.

4. Giả mã

4.1. Phân chia

Function Part(a[1..n],k1,k2)

i=k1;    
j=k2;   
k=int((k1+k2)/2)+1;   
v=a[k]    
While i<j do    
While a[i]<=v do i:=i+1;     
While a[j]>v and j>i do j=j-1;    
if i>=k2 then          
Swap(a[k],a[k2])           
return k2-1      
Swap(a[i],a[j])  
return i-1   
4.2. Sắp xếp đệ qui 

Procedure PartSort (a,k1,k2)

if k1<k2 then      
k=part(a,k1,k2)     
PartSort(a,k1,k)     
PartSort(a,k+1,k2)  
5. Khử đệ qui 
Procedure QuickSort(a[1..n])  
{   
Var list S, E;  
Int m:=1   
S(m):=1 ;  
E(m):= n;    
While m>0   
{     
k=S(m);  
l=E(m)     
m:=m-1;      
if l<l   then  
{         
i=Part(k,l);         
m=m+1;         
S(m):=i+1         
E(m):=l      
}   
}   
}   
6. Cài đặt chương trình /* Tac gia C.A.R-Hoare    -1960 */
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
char *input="day_so.inp";
float a[MAX];
int N;

void quick_sort(int l,int r)
     {
                    float tg;
                    float pivot;
                    int i,j;
                    if (l<r)                //truong hop suy bien
                      {
                            i=l;j=r;
                            pivot=a[random(r-l+1)+l];    //Các bạn đặc biệt chú ý chỗ này 
                            do
                                  {
                                       while (a[i]<pivot) i++;
                                       while (a[j]>pivot) j--;
                                       if (i<=j)   
                                          {
                                               tg=a[i];
                                               a[i]=a[j];
                                               a[j]=tg;
                                               i++;j--;
                                          }
                                  }
                            while (i<=j);
                            quick_sort(l,j);
                            quick_sort(i,r);
                       }
     }
                    
                     
void main()
    {
          FILE *f;
          int i;
          /* Doc du lieu vao tu FILE */     
          f=fopen(input,"r");
                    fscanf(f,"%d",&N);                    
                    for (i=0;i<N;i++) 
                    fscanf(f,"%f",&a[i]);
          fclose(f);
          quick_sort(0,N-1);
      /* in ra ket qua */
      printf("\n Mang sau khi da sap xep la:\n");   
          for (i=0;i<=N-1;i++)   printf("%f\n",a[i]);
          getch();

    }