[5703] in java-interest
SUN - are you listening? Please fix your Qsorts sometime this year....
daemon@ATHENA.MIT.EDU (Paul Haeberli)
Fri Feb 23 05:35:55 1996
Date: Mon, 19 Feb 1996 13:13:18 -0800
From: paul@balla.asd.sgi.com (Paul Haeberli)
To: java-interest@java.sun.com, java-interest@balla.asd.sgi.com
/*
* sortbug -
* Demonstrates a bugs in the sort funtions in "ThreeD.java" and
* in "QSortAlgorithm.java" in the Qsort demo. I hope people in the
* real world don't try to base their sorting algotithms on these
* examples, as I did.
*
* http://www.javasoft.com/applets/applets/SortDemo/QSortAlgorithm.java
*
* and
*
* http://www.javasoft.com/applets/applets/WireFrame/ThreeD.java
*
* The sort in "ThreeD.java" does not sort the sequence "534 34 768"
* correctly
*
* The sort in "QSortAlgorithm.java", recurses forever if given input
* if "6 10 10"
*
* I reported these bugs to SUN on Dec 3, 1995. 2.5 months go by, no
* reply from sun, and the problems have not been fixed.
*
* Paul Haeberl - paul@sgi.com
*
*/
import java.awt.*;
import java.lang.*;
import java.awt.image.*;
import java.util.Random;
import java.io.PrintStream;
public class Simple extends java.applet.Applet {
int con[] = new int[3];
public void init() {
int i;
con[0] = 534;
con[1] = 34;
con[2] = 0;
sort(con,0,2);
System.out.println("This works");
for(i=0; i<3; i++) {
System.out.print("pos ");
System.out.print(i);
System.out.print(" val ");
System.out.println(con[i]);
}
con[0] = 534;
con[1] = 34;
con[2] = 768;
sort(con,0,2);
System.out.println("This does not sort correctly in the version in ThreeD.java");
for(i=0; i<3; i++) {
System.out.print("pos ");
System.out.print(i);
System.out.print(" val ");
System.out.println(con[i]);
}
con[0] = 6;
con[1] = 10;
con[2] = 10;
sort(con,0,2);
System.out.println("This will not be printed!");
System.out.println("This never returns in the version in QSortAlgorithm.java");
for(i=0; i<3; i++) {
System.out.print("pos ");
System.out.print(i);
System.out.print(" val ");
System.out.println(con[i]);
}
}
/*
* This sort is from "QSortAlgorithm.java" which is like
* the one in "Matrix3D.java" which has a different bug!
*/
void sort(int a[], int lo0, int hi0) /* throws Exception */ {
int lo = lo0;
int hi = hi0;
/* pause(lo, hi); */
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;
/* pause(lo, hi); */
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
sort(a, lo0, lo);
sort(a, lo == lo0 ? lo+1 : lo, hi0);
}
}
paul haeberli
paul@sgi.com
-
This message was sent to the java-interest mailing list
Info: send 'help' to java-interest-request@java.sun.com
