Sắp xếp nhanh

Sắp xếp nhanh ("Quicksort"), còn được gọi là sắp xếp kiểu phân chia ("part sort") là một thuật toán sắp xếp phát triển bởi C.A.R. Hoarec 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 formula_1 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.
Phần tử chốt ("pivot").
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 formula_2 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:
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?
Ví dụ.
Trong ví dụ sau đây ta luôn chọn phần tử chốt là phần tử đứng giữa danh sách với chỉ số của phần tử chốt được chọn là formula_4
formula_5
Do ngẫu nhiên, phần tử chốt formula_6 là phần tử lớn nhất trong dãy, ta tìm từ trái sang phải không có phần tử nào lớn hơn phần tử chốt, do đó ta đổi phần tử chốt với phần tử cuối cùng, danh sách được chia thành hai danh sách con formula_7 và formula_8
Việc phân chia tiếp tục với danh sách conformula_9. Phần tử chốt được chọn là a[4]=1. Từ trái sang phải tìm được phần tử đầu tiên lớn hơn formula_10 là formula_11, từ phải sang phần tử đầu tiên &lt;=1 là chính a[4]. Đổi chố hai phần tử này
Đi tiếp sang phải ta được formula_12, ở phía ngược lại đi tiếp sang trái tìm được phần tử nhỏ hơn hoặc bằng chốt là chính formula_13 nhưng lúc này hai đường đã chạm nhau nên ta không đổi nữa. Do vậy formula_7 được phân chia thành hai danh sách con formula_15 và formula_16
Tiếp tục phân chia formula_16 với phần tử chốt formula_182 ta được
Tiếp tục phân chia formula_19 với phần tử chốt formula_20 ta được
Tiếp tục phân chia formula_21 với phần tử chốt formula_22 và formula_23 với phần tử chốt formula_24 ta được
Mã giả.
Thủ tục phân chia.
codice_1
Quick sort đệ quy.
codice_2
Quick sort đệ quy có sử dụng cấu trúc dữ liệu C:.
typedef int keytype;
typedef struct{
 keytype key;
}recordtype;
void Swap(recordtype *x, recordtype *y){
 recordtype temp;
 temp = *x;
 *x = *y;
 *y = temp;
int FindPivot(recordtype a[],int i, int j){
 keytype firstkey;
 int k;
 k=i+1;
 firstkey = a[i].key;
 while((k&lt;=j)&amp;&amp;(a[k].key==firstkey))
 k++;
 if(k&gt;j)
 return -1;
 else
 if((a[k].key &gt; firstkey))
 return k;
 else
 return i;
int Partition(recordtype a[],int i, int j, keytype pivot){
 int L, R;
 L=i;
 R=j;
 while(L&lt;=R){
 while (a[L].key &lt; pivot) L++;
 while (a[R].key &gt; pivot) R--;
 if (L &lt; R) Swap(&amp;a[L], &amp;a[R]);
 return L;
void QuickSort (recordtype a[], int i, int j){
 keytype pivot;
 int pivotindex, k;
 pivotindex = FindPivot(a,i, j);
 if (pivotindex != -1){
 pivot = a[pivotindex].key;
 k = Partition(a, i, j, pivot);
 QuickSort(a, i, k-1);
 QuickSort(a, k, j);
int main(){
 int n,i;
 recordtype a[50];
 printf("nhap n: ");
 scanf("%d",&amp;n);
 for(i=0;i&lt;n;i++){
 printf("nhap phan tu: ");
 scanf("%d",&amp;a[i].key);
 QuickSort(a, 0, n-1);
 for(i= 0;i&lt;n;i++){
 printf(" --- %d",a[i].key);
 return 0;
Khử đệ quy.
Nhiều người cho rằng việc khử đệ quy của sắp xếp nhanh thực ra không cần thiết, nó chỉ có tác dụng cho những người mới tiếp cận khoa học máy tính hiểu sâu sắc hơn về khái niệm đệ quy. Bản chất của các giải thuật đệ quy là lưu trữ các tham biến đệ quy vào một ngăn xếp ("stack") để lần lượt lấy ra xử lý.
Khi khử đệ quy của giải thuật đệ quy, mỗi lần phân chia danh sách thành 2 danh sách con ta lưu trữ các tham số của danh sách đứng sau vào một ngăn xếp, rồi phân chia tiếp danh sách đứng trước.
Giải thuật đơn giản nhất để khử đệ quy của sắp xếp nhanh như sau:
codice_3
Ưu điểm của sắp xếp nhanh không đệ quy nằm ở những cải tiến của giải thuật trên đây. Có thể cải tiến theo những hướng sau: Cất vào ngăn xếp danh sách con ít phần tử hơn trong hai danh sách con và đối với các danh sách con có độ dài đủ nhỏ thì dùng một phương pháp sắp xếp sơ cấp (chẳng hạn sắp xếp chèn).
Quick sort chia ba.
Một phương pháp chia khác là chia danh sách thành 3 danh sách con, lần lượt nhỏ hơn, bằng và lớn hơn phần tử chốt.
codice_4