Quicksort algorithm using Hoare’s partitioning scheme
Implement the Quicksort algorithm using Hoare’s Partitioning scheme.
As the Lomuto partition scheme is more compact and easy to understand, it is frequently used in the partition process of Quicksort. But this scheme degrades to O(n2) when the array is already sorted or when the array has all equal elements. In this post, a much more efficient Hoare partition scheme is discussed.
Hoare Partition Scheme
Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index.
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. But like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n2) 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 [low…pivot] and [pivot+1…high] as opposed to [low…pivot-1] and [pivot+1…high] as in Lomuto’s scheme.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <ctime> #include <cstdlib> using namespace std; #define N 15 // Partition using Hoare's Partitioning scheme int partition(int a[], int low, int high) { int pivot = a[low]; int i = low - 1; int j = high + 1; while (1) { do { i++; } while (a[i] < pivot); do { j--; } while (a[j] > pivot); if (i >= j) { return j; } swap(a[i], a[j]); } } // Quicksort routine void quicksort(int a[], int low, int high) { // base condition if (low >= high) { return; } // rearrange elements across pivot int pivot = partition(a, low, high); // recur on subarray containing elements that are less than the pivot quicksort(a, low, pivot); // recur on subarray containing elements that are more than the pivot quicksort(a, pivot + 1, high); } int main() { int arr[N]; srand(time(NULL)); // generate random input of integers for (int i = 0; i < N; i++) { arr[i] = (rand() % 100) - 50; } quicksort(arr, 0, N - 1); for (int i = 0; i < N; i++) { cout << arr[i] << " "; } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
import java.util.Arrays; class Main { public static void swap (int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Partition using Hoare's Partitioning scheme public static int partition(int[] a, int low, int high) { int pivot = a[low]; int i = low - 1; int j = high + 1; while (true) { do { i++; } while (a[i] < pivot); do { j--; } while (a[j] > pivot); if (i >= j) { return j; } swap(a, i, j); } } // Quicksort routine public static void quicksort(int[] a, int low, int high) { // base condition if (low >= high) { return; } // rearrange elements across pivot int pivot = partition(a, low, high); // recur on subarray containing elements less than the pivot quicksort(a, low, pivot); // recur on subarray containing elements more than the pivot quicksort(a, pivot + 1, high); } public static void main(String[] args) { int[] a = { 9, -3, 5, 2, 6, 8, -6, 1, 3 }; quicksort(a, 0, a.length - 1); // print the sorted array System.out.println(Arrays.toString(a)); } } |
Output:
[-6, -3, 1, 2, 3, 5, 6, 8, 9]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp # Partition using Hoare's Partitioning scheme def partition(a, low, high): pivot = a[low] (i, j) = (low - 1, high + 1) while True: while True: i = i + 1 if a[i] >= pivot: break while True: j = j - 1 if a[j] <= pivot: break if i >= j: return j swap(a, i, j) # Quicksort routine def quicksort(a, low, high): # base condition if low >= high: return # rearrange elements across pivot pivot = partition(a, low, high) # recur on sublist containing elements less than the pivot quicksort(a, low, pivot) # recur on sublist containing elements more than the pivot quicksort(a, pivot + 1, high) if __name__ == '__main__': a = [9, -3, 5, 2, 6, 8, -6, 1, 3] quicksort(a, 0, len(a) - 1) # print the sorted list print(a) |
Output:
[-6, -3, 1, 2, 3, 5, 6, 8, 9]
References: https://en.wikipedia.org/wiki/Quicksort
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)