Hoare’s vs Lomuto partition scheme in QuickSort

QuickSort is an efficient sorting algorithm used in computer science. This sorting algorithm is a divide and conquer approach i.e. it recursively calls itself by dividing the array into two smaller halves. It then sorts them each time until the size of the halves becomes one and the array becomes fully sorted.

Each time an array is divided, QuickSort makes use of a partition scheme as a mechanism to sort that half. A value from the array is taken as a pivot. Tthe element around which the array is partitioned he partition function makes sure that all values smaller than the pivot are shifted to its left while the larger ones are shifted to the right.

How the pivot is chosen and how the smaller and larger elements are brought to their correct places depends on the chosen partition scheme.

Two very common schemes are the Hoare's and Lomuto's schemes.

A basic implementation of Hoare's algorithm is correcting inversionsincorrect order of elements.

We first choose an arbitrary pivot such as the first or last element and make use of two variables to traverse the array from opposite ends. We then look for an element starting from the left of the array that is greater than or equal to the pivot. Similarly, we look for an element starting from the right of the array that is smaller than or equal to the pivot.

The two elements obtained are at incorrect positions and, so, are brought to their correct position by swapping.

Note: At any time, if both variables cross each other (inversion), that means that the partitioning is now complete since all smaller elements are now at the left and all larger elements are at the right.

The point at which they cross is returned as the partition value.

#include <iostream>
using namespace std;
void Swap(int* one, int* two) 
{ 
    int temp = *one;
    *one = *two;
    *two = temp;
} 
int HoarePartition(int arr[], int start, int end) {
    int pivotVal = arr[start];
    int i = start - 1;
    int j = end + 1;
    
    while (true) {
        do {
            i++;
        } while (arr[i] < pivotVal);
        
        do {
            j--;
        } while (arr[j] > pivotVal);
        
        if (i >= j) {
            return j;
        }
        
        Swap(&arr[i], &arr[j]);
    }
}
void QuickSort(int arr[], int start, int end) {
    if (start < end) {
        int pivotVal = HoarePartition(arr, start, end);
        QuickSort(arr, start, pivotVal);
        QuickSort(arr, pivotVal + 1, end);
    }
}
int main() {
  
    int arr[] = {10, 15, 8, 6, 7, 9, 1, 2, 6, 5};
    int size = 10;
    cout << "Let's sort the array [ ";
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << "] by Hoares Partition Scheme" << endl;
    QuickSort(arr, 0, size - 1);
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    
    return 0;
}

Lomuto's Algorithm

A basic implementation of Lomuto's algorithm either chooses the first or the last element as the pivot value for QuickSort's implementation.

After the pivot is selected, the remaining elements of the array are brought to their correct places with respect to the pivot i.e. smaller values to the pivot's left and larger values to the right.

Lomuto's algorithm achieves this by keeping a variable i that points to the leftmost position and then using another variable j to traverse the whole array from the left. Whenever a smaller value than the pivot is found, the elements at the two positions are swapped.

Note: Simply, if the current element is smaller than the pivot, it is brought to the leftmost position i. Then it increments by 1 since one more smaller element has been brought to its correct place.

#include <iostream>
using namespace std;
void Swap(int* one, int* two) 
{ 
    int temp = *one;
    *one = *two;
    *two = temp;
} 
int LomutoPartition(int arr[], int start, int end) {
  int pivotVal = arr[end];
  int i = start;
  for (int j = start; j < end; j++) {
    if (arr[j] <= pivotVal) {
      Swap(&arr[i], &arr[j]);
       i++;
    }
  }
  Swap(&arr[i], &arr[end]);
  return i;
}
void QuickSort(int arr[], int start, int end) {
  if (start < end) {
    int pivotVal = LomutoPartition(arr, start, end);
    QuickSort(arr, start, pivotVal - 1);
    QuickSort(arr, pivotVal + 1, end);
  }
}
int main() {
  int arr[] = {10, 15, 8, 6, 7, 9, 1, 2, 6, 5};
  int size = 10;
   cout << "Let's sort the array [ ";
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << "] by Lomuto's Partition Scheme" << endl;
  QuickSort(arr, 0, size - 1);
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
}

Time Complexity

We can understand the efficiency of each algorithm by comparing their
number of swaps. On average, Hoare's algorithm needs three times fewer swaps as compared to Lomuto's algorithm. Therefore, Hoare's is quicker and more efficient.

However, in terms of Big O, both algorithms have a time complexity of linear time $O(n)$ . This is because the array needs to be traversed at least once.

Thus, the average time complexity for QuickSort would be $O(nlogn)$ for both partition schemes.