QuickSort
Richard A. O'Keefe
ok at atlas.otago.ac.nz
Tue Dec 4 03:26:38 UTC 2001
"James Stark" <james_stark03 at hotmail.com> wrote:
quicksort: begin to: end
Which class is this from?
pivot := self basicAt: middle.
I am always suspicious of code that uses #basicAt:. It should be rare.
I can confrim that this algorithm does not work - its crap.
I take it that this means you have a test case which it gets wrong?
Actually its
meant to assign the pivot value to the left to start off with.
You need to be aware that there are many variants of quicksort. Quite
a few of them don't do that.
If any of you guys have developed any other algortihms it would be
interesting to do a trace. Like a binary tree sort (is that more
efficient?) I dont know... just traced that one - made no sense.
Sense shmense. Did it give the right answer?
If you poke around in Squeak 3.0, you will find
- a quicksort in SortedCollection>>sort:to:
- a Heap Sort example in SortedCollection class>>heapSortExample
- a merge sort in ArrayedCollection>>sort:
Merge sort is a good general-purpose sorting method which, if written
carefully, can easily out-perform quick-sort. (Yes yes, I know the papers
that are supposed to prove quicksort fast. They assume that comparisons
are dirt cheap; in one paper 1/4 of the cost of a memory reference. In a
system like Squeak where comparison blocks are involved, comparisons are
not cheap.)
More information about the Squeak-dev
mailing list
|