Bozo Sort
Some of the first compelling Java demos were graphical illustrations of several sorting methods including quick sort, bubble sort and bidirectional bubblesort intended to show off the threading capabilities of Java. That’s nice, but those methods eventually succeed within our lifetime. For an applet that truly puts threading to good use consider the following bozo sort. In bozo sort the same collection of differently sized sticks is thrown up in the air. If they land in sorted order, the algorithm stops. Otherwise we throw all the sticks in the air again. This algorithm runs in about O(N!) time where N is the number of sticks. It takes effectively infinite time for more than a dozen or so sticks. It’s a horrible algorithm but a really great opportunity for threading.
class BozoSortAlgorithm extends SortAlgorithm {
void sort(int a[]) {
boolean sorted = false;
while (!sorted) {
int index1 = Randomize(a.length);
int index2 = Randomize(a.length);
int temp = a[index2];
a[index2] = a[index1];
a[index1] = temp;
// Is a[] sorted?
sorted = true;
for (int i = 1; i < a.length; i++) {
if (a[i-1] > a[i]) {
sorted = false;
break;
} // end if
} // end for
} // end while
} // end sort
private int Randomize( int range ) {
double rawResult;
rawResult = Math.random();
return (int) (rawResult * range);
}
} // end BozoSortAlgorithm
To actually run this you’ll also need the SortItem and SortAlgorithm classes from Sun.