Sorting :)

Roseann R. Krane (rkrane@monte.mvhs.srvusd.k12.ca.us)
Wed, 16 Oct 1996 01:00:22 -0700 (PDT)


I thought you all might enjoy this. I had never heard of Bozo sort
before. I think we should teach it to the CS AB before the AP test!

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.

I also suggest that java demonstrations of different sort methods would be
very instructive, especially trying to learn Big O.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~ Roseann Rayes Krane, http://www.mvhs.srvusd.k12.ca.us/~rkrane ~
~ Monte Vista High School, Network Manager, 510-552-2859 ~
~ Teacher, Computer Science Department, 510-837-7507 ~
~ ~
~ "All students are different, schools should make them more so!" ~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~