Ý tưởng:
Gần giống như merge sort , ta sẽ chia đôi mảng cần xếp rồi sắp xếp các mảng con , sau đó sẽ ghép mảng con đã sắp xếp thành mảng ban đầu nhưng đã sắp xếp

Điểm khác nhau: Là chổ ta chia đôi mảng con theo nguyên tắc riêng :
Gọi điểm mà tại đó ta chia đôi mảng ban đầu có trị là pivot (không nhất thiết là nằm đúng vị trí chính giữa . Nhưng giải thuật sẽ chạy tốt nếu nó nằm gần điểm chính giữa) và ta sẽ không cần merge 2 dãy con (do đó nhìn chung sẽ chạy nhanh hơn ) , thỏa điều kiện là tất cả những phần tử bên trái pivot đều nhỏ hơn pivot và nằm bên phải pivot thì lớn hơn pivot

VD :
2 4 6 7 18 14 13
Ta chọn phần tử pivot = 7 ( do bên trái của nó nhỏ hơn pivot = 7 , bên phải lớn hơn pivot = 7 ) (Thực ra ta phải tìm pivot , do ở đây làm bằng tay nên dễ thấy )
Chia đôi : A = { 2 4 6 } B = { 18 14 13 }
+ Sắp A
+ Trong dãy A ta cũng chọn phần tử pivot là 4
+ Được 2 dãy con là A11 = {2 } A12 = {6}
+ Sắp A11 ( sắp sẵn rồi )
+ Sắp A12 ( sắp sẵn rồi )
+ Tạo lại mảng A = { A11 được sắp , pivot , A12 được sắp } = {2 4 6 }
+Sắp B . Trong B ta không thấy được pivot do chọn cái nào ta cũng không thấy thỏa . Nhưng mục tiêu của quick sort là làm sao ta được dãy
<C= dãy có trị nhỏ hơn pivot > pivot < D= dãy có trị lớn hơn pivot >
Sắp 2 dãy con C , D rồi ghép lại ta được dãy sắp thứ tự .


Vì vậy áp dụng một giải thuật tìm pivot trong B( sẽ trình bày sau ) ta sẽ được C = { 13} D = {18} và pivot là 14 .
+ Sắp dãy con C , D ( do chỉ có một phần tử nên không sắp , hoặc tìm pivot)
+ Ghép lại tạo thành mảng B được sắp B = { 13 14 18 }

+Ghép A và B để tạo thành mảng được sắp xếp ban đầu
 

void Sortable_List<Record>::quick_sort()

 {

           recursive_quick_sort(0 , count -1 ) ;

 }

 

 void Sortable_List<Record>::recursive_quick_sort(int low , int high )

 {

           int pivot_position ;

           if (low < high )

           {

                     pivot_position = partition (low , high ) ;

                     recursive_quick_sort(low , high ) ;

                     recursive_quick_sort(pivot_position +1 , high ) ;

           }

 }

 

 

 int Sortable_List<Record>::partition(int low , int high ) 

 {

               Record pivot ;

               int i , last_small;

               swap ( low , (low +high) /2 ;

               pivot = entry[low] ;

               last_small = low ;

               for ( i = low +1 ; i <= high ; i ++ )

               {

                         if(entry[i] < pivot )

                         {

                                     last_small = last_small +1 ;

                                     swap ( last_small , i ) ;

                         }

                 

               }

                 swap (low , last_small );

                 return last_small ;

 }