Gosling's quicksort freezes

[hiwa]

If there are duplicate values in the data set, James Gosling's
QSortAlgorithm does freeze. What should be the cause and what
could be the solution?

Here's a test program:

public class GoslingQsort{
public static void main(String[] args){
int[] data1 = {68, 0, 54, 26, 6, 54, 57, 35, 9, 45}; //freezes
int[] data2 = {68, 0, 54, 26, 6, 14, 57, 35, 9, 45}; //normal
int[] data = args.length > 0 ? data2 : data1; //you can
//compare
printArray("initial", data);
QSortAlgorithm qsa = new QSortAlgorithm();
qsa.sort(data);
printArray("result ", data);
}

static void printArray(String s, int[] a){
System.out.print(s + ": ");
for (int i = 0; i < a.length; ++i){
System.out.print(a + " ");
}
System.out.println();
}
}

/**
* A quick sort demonstration algorithm
* @author James Gosling
* @history Modified by Pat Morin, 7 Feb 1996
*/
class QSortAlgorithm {

/*Uses quick sort to sort the array between the specified
indices*/
void sort(int a[], int lo0, int hi0){
int lo = lo0;
int hi = hi0;
if (lo >= hi) {
return;
}
int mid = a[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && a[lo] < mid) {
lo++;
}
while (lo<hi && a[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
sort(a, lo0, lo);
sort(a, lo == lo0 ? lo+1 : lo, hi0);
}

/*Sorts the given array using the quicksort algorithm.*/
void sort(int a[]){
sort(a, 0, a.length-1);
}
}

 

[JScoobyCed]

If there are duplicate values in the data set, James Gosling's
QSortAlgorithm does freeze. What should be the cause and what
could be the solution?

In the algorithm code, if:
a[lo] == a[hi] == mid

--> you run the main while() loop indefinitely as no value will be
changed, but a[lo] and a[hi] will be switched (and as they are equals,
they will be switched indefinitely)

 

[Thomas Weidenfeller]

If there are duplicate values in the data set, James Gosling's
QSortAlgorithm does freeze. What should be the cause and what
could be the solution?

while (lo < hi) {
while (lo<hi && a[lo] < mid) {
lo++;
}
while (lo<hi && a[hi] > mid) {
hi--;
}

This loop does not terminate if

lo < hi && (a[lo] >= mid) && (a[hi] <= mid)

Because in this case the indices into the partitions are no longer
advanced. This happens e.g. if

lo < hi && (a[lo] == a[hi] == mid)

Which means, if you got an unlucky pick of the partitioning element
"mid" and then hit the same value both in the left and right partition
at the same time its game over.

The loop is much different in Gosling's original code. So whoever this
Pat Morin is, he introduced a bunch of new and improved bugs when
"improving" the code. You find the original one in your JDK installation
somewhere in the demo/applets directory.

But Gosling's code is not the most elegant quicksort implementation I
have seen. Sedgewick has a very nice one in his Algorithms in <insert
random language> series of books.

/Thomas

 

[hiwa]

If there are duplicate values in the data set, James Gosling's
QSortAlgorithm does freeze. What should be the cause and what
could be the solution?

while (lo < hi) {
while (lo<hi && a[lo] < mid) {
lo++;
}
while (lo<hi && a[hi] > mid) {
hi--;
}

This loop does not terminate if

lo < hi && (a[lo] >= mid) && (a[hi] <= mid)

Because in this case the indices into the partitions are no longer
advanced. This happens e.g. if

lo < hi && (a[lo] == a[hi] == mid)

Which means, if you got an unlucky pick of the partitioning element
"mid" and then hit the same value both in the left and right partition
at the same time its game over.

The loop is much different in Gosling's original code. So whoever this
Pat Morin is, he introduced a bunch of new and improved bugs when
"improving" the code. You find the original one in your JDK installation
somewhere in the demo/applets directory.

But Gosling's code is not the most elegant quicksort implementation I
have seen. Sedgewick has a very nice one in his Algorithms in <insert
random language> series of books.

/Thomas

Thanks Thomas, again.
Your are The Encyclopedia of Java Documentation Resources.

Viewing Gosling's QSortAlgorithm.java 1.11 04/07/26
in the JDK 1.5.0_01, I have noticed that the solution
is adding

++lo; --hi;

after the swap.

Sedgewick's pre-increment of indices, which are post-incremented
in Gosling's loop, has the same sound effect.

 

[Esmond Pitt]

The loop is much different in Gosling's original code. So whoever this
Pat Morin is, he introduced a bunch of new and improved bugs when
"improving" the code.

On this evidence neither Gosling nor Pat Morin understands the Quicksort
algorithm at all. There aren't supposed to be range-checks in the inner
loops: this is where all the performance comes from.