QuickSort

Jerzy Karczmarczuk karczma at info.unicaen.fr
Tue Dec 4 09:25:16 UTC 2001


James Stark:
> 
> quicksort: begin to: end

...

> I can confrim that this algorithm does not work - its crap.  It starts from
> the middle?  thats not how quicksort is meant to work, its meant to start
> from the sides (left and right) and when they cross over it meant to assign
> the pivot value.  Actually its meant to assign the pivot value to the left
> to start off with.


I didn't test the algorithm, so I cannot say whether it works or not.
However, calling it a crap just because it doesn't correspond to the 
limited vision of the author what the quicksort is and what isn't seems
a bit rude.

In quicksort you have the right to choose ANY element as your pivot.
A classical bidirectional loop is somehow slightly optimized when the
choice of the pivot is the LAST element; if you use lists, than the 
natural choice is the first element, and there is no bidir. loop, but the
partitioning of the list in two. Etc. etc.

Please think twice before saying "thats not how quicksort is meant to work".
Independently of the quality of the quoted algorithm, which I won't argue
about. But I would like to see a concrete test, instead of "I traced it, it
makes no sense".

Binary, arborescent sort usually is reputed to be a bit less efficient than
quicksort anyway. Richard O'Keefe said more about the current situation in
Squeak.

Jerzy Karczmarczuk
Caen, France




More information about the Squeak-dev mailing list