Quicksort - Hoare's partitioning with duplicate values
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j – 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
The pseudocode above is taken from Wikipedia. Let's compare it with your code.
The problem is that you have to move the indices after the swap. The pseudocode uses do-while
loop instead of while
loop to move the indices after the swap. Also pay attention to the initial values of i
and j
.
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
For the recursive step, you might need to take care of the edge cases (i.e., the indices). It should work if you change quicksort(a, lo, q-1)
to quicksort(a, lo, q)
.
A complete working version I just wrote:
import java.util.Arrays;
public class Test {
public static void main(String[] args) throws Exception {
int[] input = {1, 57, 1, 34};
quicksort(input, 0, input.length - 1);
System.out.println(Arrays.toString(input));
}
private static void quicksort(int[]a, int lo, int hi) {
if (lo < hi) {
int q = hoare_partition(a, lo, hi);
quicksort(a, lo, q);
quicksort(a, q + 1, hi);
}
}
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo - 1;
int j = hi + 1;
while (true) {
do {
i++;
}
while (a[i] < pivot);
do {
j--;
}
while (a[j] > pivot);
if (i >= j) {
return j;
}
swap(a, i, j);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
If you prefer the while
loop instead of do-while
:
private static int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[lo];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i >= j) {
return j;
}
swap(a, i, j);
i++;
j--;
}
}
Here is a C++ example that implements Hoare scheme plus a median of 3 check, a duplicate of pivot check to exclude middle values equal to pivot (note that values equal to pivot can end up anywhere, not just the middle, so this doesn't help much), only using recursion on the smaller part, looping back for the larger part (this prevents stack overflow). Worst case time complexity is still O(n^2), but it takes fairly specific data patterns to produce this (median of 3 would have to consistently keep picking near smallest or near largest values).
void QuickSort(uint32_t a[], size_t lo, size_t hi) {
while(lo < hi){
size_t i = lo, j = (lo+hi)/2, k = hi;
uint32_t p;
if (a[k] < a[i]) // median of 3
std::swap(a[k], a[i]);
if (a[j] < a[i])
std::swap(a[j], a[i]);
if (a[k] < a[j])
std::swap(a[k], a[j]);
p = a[j];
i--; // Hoare partition
k++;
while (1) {
while (a[++i] < p);
while (a[--k] > p);
if (i >= k)
break;
std::swap(a[i], a[k]);
}
i = k++;
while(i > lo && a[i] == p) // exclude middle values == pivot
i--;
while(k < hi && a[k] == p)
k++;
// recurse on smaller part, loop on larger part
if((i - lo) <= (hi - k)){
QuickSort(a, lo, i);
lo = k;
} else {
QuickSort(a, k, hi);
hi = i;
}
}
}