Quicksort

#algorithm

Quicksort is a very commonly used sorting algorithm due to its efficiency.

The main idea of the algorithm is: pick a pivot element, then partition the elements of the array into two halves around that pivot, each half will be sorted recursively until everything is sorted.

The following algorithm has the best case time complexity of O(n log n) and worst case is O(n^2).

int function Partition (Array A, int Lb, int Ub);    
  begin                                              
  select a pivot from A[Lb]...A[Ub];                 
  reorder A[Lb]...A[Ub] such that:                   
    all values to the left of the pivot are <= pivot 
    all values to the right of the pivot are >= pivot
  return pivot position;                             
  end;                                               
                                                     
procedure QuickSort (Array A, int Lb, int Ub);       
  begin                                              
  if Lb < Ub then                                    
    M = Partition (A, Lb, Ub);                       
    QuickSort (A, Lb, M - 1);                        
    QuickSort (A, M + 1, Ub);                        
  end;                                               

About the partition algorithm, there are two well known schemes:

1. Lomuto Partition Scheme:

function partitionLomuto(array, left, right) { 
  var pivot = right;                           
  var i = left;                                
  for(var j = left; j < right; j++) {          
    if(array[j] <= array[pivot]) {             
      swap(array, i , j);                      
      i = i + 1;                               
    }                                          
  }                                            
  swap(array, i, j);                           
  return i;                                    
}                                              

2. Hoare Partition Scheme:

function partitionHoare(array, left, right) {   
  var pivot = Math.floor((left + right) / 2 );  
  while(left <= right) {                        
    while(array[left] < array[pivot]) {         
      left++;                                   
    }                                           
    while(array[right] > array[pivot]) {        
      right--;                                  
    }                                           
    if(left <= right) {                         
      swap(array, left, right);                 
      left++;                                   
      right--;                                  
    }                                           
  }                                             
  return left;                                  
}                                               

For comparision between the two schemes:

• Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.
• Like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n^2) when the input array is already sorted, it also doesn’t produce a stable sort.
• Note that in this scheme, the pivot’s final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto’s scheme.