Re: quicksorts [Re: List sorting dilemma]
Re: quicksorts [Re: List sorting dilemma]
- Subject: Re: quicksorts [Re: List sorting dilemma]
- From: Paul Berkowitz <email@hidden>
- Date: Fri, 26 Jul 2002 13:03:53 -0700
On 7/26/02 12:09 PM, "Arthur J. Knapp" <email@hidden> wrote:
>
I hate to do this to you, Has, but my more recent quicksorts are
>
considerably faster than the one you posted above:
>
>
on QuickSort(a, l, r)
>
(*
>
* Sorts "in-place":
>
*
>
* set a to { 2, 3, 1 }
>
*
>
* QuickSort( a, 1, a's length ) -- no return value
>
*
>
* get a --> { 1, 2, 3 }
>
*)
>
>
local i, j, v --> SD debugging
>
>
(* Much thanks to Serge Belleudy-d'Espinose for that
>
* extra surge of speed. :)
>
*)
>
script o
>
property p : a
>
end script
>
>
set i to l
>
set j to r
>
set v to o's p's item ((l + r) div 2)
>
>
repeat while (j > i)
>
>
repeat while (o's p's item i < v)
>
set i to i + 1
>
end repeat
>
>
repeat while (o's p's item j > v)
>
set j to j - 1
>
end repeat
>
>
if (not i > j) then
>
>
(* set { i, j } to { j, i }
>
*)
>
set o_s_p_s_item_i to o's p's item i
>
set o's p's item i to o's p's item j
>
set o's p's item j to o_s_p_s_item_i
>
>
set i to i + 1
>
set j to j - 1
>
>
end if
>
end repeat
>
>
if (l < j) then QuickSort(o's p, l, j)
>
if (r > i) then QuickSort(o's p, i, r)
>
>
end QuickSort
>
>
>
Of course, no matter how fast we make them, all vanilla sorting
>
routines are still pretty darn slow for large lists. :(
How does this compare with Emanuel's post-Serge latest version:
on sort(theList)
-- (with credits to SBE & FD)
set theLength to theList's length
if theLength = 0 or theLength = 1 then return theList
if theLength = 2 then
set {xItem, yItem} to theList
if xItem > yItem then return {yItem, xItem}
return theList
end if
script listHolder
property theList : {}
property lowList : {}
property highList : {}
end script
set listHolder's theList to theList
set xMiddle to (theLength + 1) div 2
set xMedian to listHolder's theList's item xMiddle
repeat with i from 1 to (xMiddle - 1)
set xItem to listHolder's theList's item i
if xItem < xMedian then
set listHolder's lowList's end to xItem
else
set listHolder's highList's end to xItem
end if
end repeat
repeat with i from (xMiddle + 1) to theLength
set xItem to listHolder's theList's item i
if xItem < xMedian then
set listHolder's lowList's end to xItem
else
set listHolder's highList's end to xItem
end if
end repeat
if listHolder's lowList's length > 1 then set listHolder's lowList to
sort(listHolder's lowList)
if listHolder's highList's length > 1 then set listHolder's highList to
sort(listHolder's highList)
return listHolder's lowList & xMedian & listHolder's highList
end sort
--
Paul Berkowitz
_______________________________________________
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.