Understanding Quick Sort and QuickSelect using Hoare Partition
This class implements a QuickSort algorithm using Hoare Paritioning scheme. This partitionining scheme is slightly harder to implement but is more efficient than the Lamuto partitioning scheme as it does three times fewer swaps on average [Wikipedia].
- Avg Time-Complexity: O(nlogn)
- Worst Time-Complexity: O(n^2)
- Space complexity: O(1)
Understanding Hoare Partition Intuitively
After spending quite some on the two, this StackExchange post nailed the key idea of Hoare Partition. Kartikey Gupta wrote,
“Lomuto divides the array into three parts; elements smaller than the pivot, the pivot, elements greater than the pivot. I think Hoare looks at things differently. He divides the array into two parts; elements smaller than the pivot, elements equal to or greater than the pivot. One of the traps that I fell into was that Lomuto’s partition returns the final position of the pivot, whereas Hoare’s partition returns the position just before the final position of the pivot. This is why Lomuto then quick sorts from
lo
top-1
, whereas Hoare quick sorts fromlo
top
. Another inference that can be drawn is that if Hoare’spartition
returnedi
instead ofj
, we’d then divide the array into two parts- fromlo
toi-1
and fromi+1
tohi
, just like Lomuto did. And it only took me 4 hours to understand that.” [cs.stackexchange.com]
Implementation in Java
<pre class="wp-block-code">```java
public class QuickSortHoare{
int[] arr;
public QuickSortHoare(int[] arr){
this.arr = arr;
}
private void sort(int i, int j) {
if (i < j) {
int p = partition(i, j);
sort(i, p);
sort(p+1, j);
}
}
private void sort(){
sort(0, arr.length-1);
}
private int partition(int left, int right) {
int pivot = (left+right)/2;
int pivotValue = arr[pivot];
int i = left-1;
int j = right+1;
while(true){
do {
i++;
} while( arr[i] < pivotValue);
do {
j--;
} while( arr[j] > pivotValue );
if (i<j) {
swap(i, j);
} else {
return j;
}
}
}
private void swap(int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
Resources
A good reference is here by Michael Cotterell%20).) however it returns the low pointer from the partitioning which is requires that the recursive sorting is done on [low: partition-1] and [partition+1: high]