Hi All,

While reading this thread i dug out my scriptum for the 'Effiziente
Algortihmen' course I took several years ago and found 'HeapSort', an
algorithm that behaves nicely with respect to previously ordered
collections and deals with simple additions rather nicely. So i coded it
up (with the stream protocol of course). I didn't test it thouroughly
though and there may be bugs or misconceptions in my code that prevent
it from being that performatn but I'll post it here whatsoever. So at
least our poor guy (who wanst us to make his homework/suffers from an
arrogant superviser/doesn't know the first thing about smalltalk) can
use it for his work.

Usage is:
SortedStream new (It doesn't really stream over anything so this makes
sense)
SortedStream sortBlock: aBlock
SortedStream on: aCollection (is copied on instance creation)
SortedStream on: aCollection sortBlock: aBlock
I'll mark this as a ToDo since people might be confused if they open a
SortedStream with #on:.

Hope this helps,
Torge

"Andrew C. Greenberg" wrote:
> 
> On Sunday, November 18, 2001, at 09:14  PM, Richard A. O'Keefe wrote:
> 
> >       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.
> 
> Indeed, and the worst case behavior actually arises in an annying, but
> fairly common, scenario: where the array is already sorted.  Because of
> the low coefficient, Quicksort is beneficial in some cases since it
> behaves like an nlogn sort on average, but it is certainly not best for
> general purpose code where a sorted, or almost-sorted, array is more
> likely to be presented.
> 
> Many commercial Quicksort codes impose a random permutation on the array
> before processing, so that the worst case behavior occurs less
> frequently in scenarios where arrays arrive nearly sorted.  Still, this
> doesn't make the code better than it is -- it will still wait
> interminably for some large tables on some occasions.
> 
> > 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.
> 
> Indeed, QS is a nightmare for simple additions to substantially
> pre-sorted arrays.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MySorting.2.cs
Type: application/octet-stream
Size: 6275 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20011120/a5a9f254/MySorting.2.obj