Re: Please Pass the Handler
Re: Please Pass the Handler
- Subject: Re: Please Pass the Handler
- From: "Serge Belleudy-d'Espinose" <email@hidden>
- Date: Mon, 14 Jan 2002 16:29:36 +0100
At 14:38 +0000 14/01/02, has wrote:
>
>If it is, I realize
>
>that qsort can be implemented with loops though IIRC it's a serious
>
>brain-buster to follow. Maybe one of my old algorithms books has the
>
>necessary code.
>
>
I'd be interested to see if you came up with a non-recursive quicksort.
>
I've tested Serge's quicksort against both a binary insertion sort and a
>
bubble sort for interest, and the damn thing's so fast it's done before the
>
other two have even started.<g> So, needless to say, a totally unbreakable
>
qsort would be my absolute idea of heaven.
There must be a bell in my head that rings everytime someone somewhere uses the word qsort...
Just for fun I tried to write a non-recursive qsort. It's about 4x slower, having to deal with piling everything up and down, but at least it works.
Please feel free to play with it and improve it as you will.
--
to singleSort(pList)
try
set pList to contents of (pList as list)
on error
error "singleSort(): parameter must be a list"
end try
script lObject
property lMain : pList
property lStack : {}
property iStack : {}
property lResult : {}
end script
tell lObject
repeat
set lLength to (length of its lMain)
if lLength < 2 then
set its lResult to (its lResult & its lMain)
if its lStack = {} then
exit repeat
else
set {leftItem, rightItem} to (last item of its lStack)
set its lResult to (its lResult & leftItem)
set its lMain to rightItem
set its lStack to (reverse of rest of reverse of its lStack) -- pile down
end if
else if lLength = 2 then
if (item 1 of its lMain) > (item 2 of its lMain) then
set its lResult to (its lResult & reverse of its lMain)
else
set its lResult to (its lResult & its lMain)
end if
if its lStack = {} then
exit repeat
else
set {leftItem, rightItem} to (last item of its lStack)
set its lResult to (its lResult & leftItem)
set its lMain to rightItem
set its lStack to (reverse of rest of reverse of its lStack) -- pile down
end if
else -- lLength > 2
set iMedian to (item ((lLength + 1) div 2) of its lMain)
set its iStack to {{}, {}, {}}
repeat with i from 1 to lLength
set iItem to item i of its lMain
if iItem < iMedian then
set (end of (item 1 of its iStack)) to iItem
else if iItem = iMedian then
set (end of (item 2 of its iStack)) to iItem
else
set (end of (item 3 of its iStack)) to iItem
end if
end repeat
set {its lMain, (end of its lStack)} to {item 1 of its iStack, (rest of its iStack)} -- pile up
end if
end repeat
its lResult
end tell
end singleSort
Serge
--
\\//\//\// Serge Belleudy-d'Espinose Institut Jacques Monod
// // //
http://www.ijm.jussieu.fr/ Universite Paris VII - Jussieu
//\//\//\\