quicksorts [Re: List sorting dilemma]
quicksorts [Re: List sorting dilemma]
- Subject: quicksorts [Re: List sorting dilemma]
- From: has <email@hidden>
- Date: Fri, 26 Jul 2002 14:24:46 +0100
Ethan wrote:
>
I'm able to access the list of files, but in attempting to use a quicksort
>
implementation (posted a while back by Arthur Knapp-not that he's
>
responsible for any of my -er- results), the quicksort handler gets a stack
>
error.
The quicksort code you posted was faulty. Due to their recursive nature,
all quicksort algorithms will eventually suffer stack overflows if given a
large enough list, but thanks to a couple bugs this one was getting stuck
in an infinitely recursing loop. Here's the fixed version:
======================================================================
to quicksort(Lst, a, z)
copy {a, z, Lst's item ((a + z) div 2)} to {l, r, val}
repeat until r is less than or equal to l
repeat while Lst's item l < val
copy l + 1 to l
end repeat
repeat while Lst's item r > val
copy r - 1 to r
end repeat
if l is less than or equal to r then copy {Lst's item l, Lst's
[NO-BREAK]item r, l + 1, r - 1} to {Lst's item r, Lst's item l, l, r}
end repeat
if a < r then quicksort(Lst, a, r)
if z > l then quicksort(Lst, l, z)
Lst
end quicksort
======================================================================
While we're on the topic, here is possibly the ugliest AS quicksort routine
yet devised. Similarities to Serge's earlier quicksorts should be obvious
enough, but I've reworked the loops to improve speed another 5-10%. Ahh,
the evil we do in the name of speed...
======================================================================
on _quickSort(theList)
script kludge
property kList : theList
property lesserList : {}
property greaterList : {}
end script
tell kludge
set listLength to (count its kList)
set midpointIndex to (listLength + 1) div 2
set thePivot to its kList's item midpointIndex
repeat with x from 1 to (midpointIndex - 1)
get its kList's item x
if result is less than thePivot then
set its lesserList's end to result
else
set its greaterList's end to result
end if
get its kList's item -x
if result is less than thePivot then
set its lesserList's end to result
else
set its greaterList's end to result
end if
end repeat
if (listLength - midpointIndex) is midpointIndex then
get its kList's item -midpointIndex
if result is less than thePivot then
set its lesserList's end to result
else
set its greaterList's end to result
end if
end if
if (count its lesserList) is greater than 1 then set its
[NO-BREAK]lesserList to my _quickSort(its lesserList)
if (count its greaterList) is greater than 1 then set its
[NO-BREAK]greaterList to my _quickSort(its greaterList)
return its lesserList & thePivot & its greaterList
end tell
end _quickSort
on quickSort(theList)
if theList's class is not list then error "Not a list."
if (count theList) is greater than 1 then
return _quickSort(theList)
else
return theList
end if
end quickSort
======================================================================
Ugly mother, but worth a clipping as you never know when these things might
be useful. And it beats the tar out of the [non-optimised] in-place sort
above.
has
--
http://www.barple.connectfree.co.uk/ -- The Little Page of Beta AppleScripts
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.