I have implemented the classic Hoare's partitioning algorithm for Quicksort. It works with any list of unique numbers [3, 5, 231, 43]. The only problem is when I have a list with duplicates [1, 57, 1, 34]. If I get duplicate values I enter an infinite loop.
private void quicksort(int[]a, int lo, int hi) {
if (lo < hi) {
int q = hoare_partition(a, lo, hi);
quicksort(a, lo, q - 1);
quicksort(a, q + 1, hi);
}
}
private int hoare_partition(int[] a, int lo, int hi) {
int pivot = a[hi];
int i = lo;
int j = hi;
while (true) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i < j) swap(a, i, j);
else return j;
}
}
Is it possible that Hoare's implementation is incorrect and is unable to cope with duplicates?
I know this has been asked many times (and I tried them all) but I am having difficulties figuring the solution for this implementation.
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--;
}
}