Sắp xếp nhanh

Thủ tục phân chia

// left là chỉ số của phần tử đầu tiên của mảng
  // right là chỉ số của phần tử cuối cùng của mảng
  // số phần tử của mảng = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
   1.'pivotValue':= array['pivotIndex']
   2.swap array['pivotIndex'] and array['right']  // Move pivot to end
   3.'storeIndex':= 'left'
   4.for 'i' from 'left' to 'right'-1  // left ≤ i < right
         1.if array['i'] < 'pivotValue'
             1.swap array['i'] and array['storeIndex']
             2.'storeIndex':= 'storeIndex' + 1
   5.swap array['storeIndex'] and array['right']  // Move pivot to its final place
   6.return 'storeIndex'

Quick sort đệ quy

function quicksort(array, 'left', 'right')
     // If the list has 2 or more items
     if 'left' < 'right'
         // See "Choice of pivot" section below for possible choices
         choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'
         // Get lists of bigger and smaller items and final position of pivot
         'pivotNewIndex':= partition(array, 'left', 'right', 'pivotIndex')
         // Recursively sort elements smaller than the pivot
         quicksort(array, 'left', 'pivotNewIndex' - 1)
         // Recursively sort elements at least as big as the pivot
         quicksort(array, 'pivotNewIndex' + 1, 'right')

Quick sort đệ quy có sử dụng cấu trúc dữ liệu C:

1 #include<stdio.h> 2 #include<conio.h> 3 typedef int keytype; 4 typedef struct{ 5 keytype key; 6 }recordtype; 7 void Swap(recordtype *x, recordtype *y){ 8 recordtype temp; 9 temp = *x;10 *x = *y;11 *y = temp;12 }13 int FindPivot(recordtype a[],int i, int j){14 keytype firstkey;15 int k;16 k=i+1;17 firstkey = a[i].key;18 while((k<=j)&&(a[k].key==firstkey))19 k++;20 if(k>j)21 return -1;22 else23 if((a[k].key > firstkey))24 return k;25 else26 return i;27 }28 int Partition(recordtype a[],int i, int j, keytype pivot){29 int L, R;30 L=i;31 R=j;32 while(L<=R){33 while (a[L].key < pivot) L++;34 while (a[R].key > pivot) R--;35 if (L < R) Swap(&a[L], &a[R]);36 }37 return L;38 }39 void QuickSort (recordtype a[], int i, int j){40 keytype pivot;41 int pivotindex, k;42 pivotindex = FindPivot(a,i, j);43 if (pivotindex != -1){44 pivot = a[pivotindex].key;45 k = Partition(a, i, j, pivot);46 QuickSort(a, i, k-1);47 QuickSort(a, k, j);48 49 }50 }51 int main(){52 int n,i;53 recordtype a[50];54 printf("nhap n: ");55 scanf("%d",&n);56 for(i=0;i<n;i++){57 printf("nhap phan tu: ");58 scanf("%d",&a[i].key);59 }60 QuickSort(a, 0, n-1);61 for(i= 0;i<n;i++){62 printf(" --- %d",a[i].key);63 }64 return 0;65 }

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:
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<k  then {
       i=Part(k,l);
       m=m+1;
       S(m):=i+1
       E(m):=l
    }
 }
 }
Ư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.
function quicksort(a)
   Var list less, equal, greater
    if length(a) ≤ 1
        return a
    else
        select a pivot value pivot from a
        for each x in a
            if x < pivot then add x to less
            if x = pivot then add x to equal
            if x > pivot then add x to greater
        return concatenate(quicksort(less), equal, quicksort(greater))