QuickSort
James Stark
james_stark03 at hotmail.com
Tue Dec 4 00:24:07 UTC 2001
quicksort: begin to: end
| pivot i j temp middle |
i := begin.
j := end.
middle := (i + j) // 2.
pivot := self basicAt: middle.
[ i > j ] whileFalse: [
[ temp := self basicAt: i.
(sortBlock value: pivot value: temp) not
and: [ sortBlock value: temp value: pivot ]
] whileTrue: [ i := i + 1 ].
[ temp := self basicAt: j.
(sortBlock value: temp value: pivot) not
and: [ sortBlock value: pivot value: temp ]
] whileTrue: [ j := j - 1 ].
(i <= j) ifTrue: [
(i == j) ifFalse: [
temp := self basicAt: i.
self basicAt: i put: (self basicAt: j).
self basicAt: j put: temp.
].
i := i + 1.
j := j - 1
]
].
(begin < j)
ifTrue: [ self quicksort: begin to: j ].
(i < end)
ifTrue: [ self quicksort: i 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.
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.
Thanks,
James
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp
More information about the Squeak-dev
mailing list
|