Here is a challenge for you :-)

Richard A. O'Keefe ok at atlas.otago.ac.nz
Mon Nov 19 02:14:36 UTC 2001


"Christopher K Roach" <chrisroach at btinternet.com> wrote:
	Sorting Algorithm,
	
	I am not allowed to use the SortedCollection type.
	
Who does not allow this, and what is their reason for this?

	Can you do the below without using SortedCollection, is that possible?  Ya

What exactly do you want to do?

Let's suppose the task is
    "Given some kind of collection, produce a sorted version of it."

Fire up a method finder, and look for 'sort'.
You'll find #sort and #sort: in ArrayedCollection.

So:
	sorted := theUnsortedCollection asArray.
	sorted sort.
or
	sorted sort: [:a :b| "whatever it takes to do <="].

There is just no point in implementing quicksort yourself.

	quicksort: begin to: end
	    "This is an implementation of the Quick Sort algorithm, which
	     is O(n*log(n)), where n is the size of the collection to
	     be sorted."
	
The order-of-magnitude claim is FALSE.  Quicksort is O(N**2).
The worst case does arise in practice.  The #sort[:] methods already
in ArrayedCollection do not have that problem.

SortedCollection is supposed to maintain a collection in order as one
adds things to it.  I suspect that simply letting it get out of order
and _lazily_ resorting it using some method that exploits existing
order (such as natural merge, or perhaps SplaySort) might be better.





More information about the Squeak-dev mailing list