Re: Sort a List with Integers & Letters
Re: Sort a List with Integers & Letters
- Subject: Re: Sort a List with Integers & Letters
- From: "Nigel Garvey" <email@hidden>
- Date: Tue, 3 Apr 2007 20:33:52 +0100
Jon Pugh wrote on Tue, 3 Apr 2007 09:01:47 -0700:
>At 9:57 PM +0100 4/2/07, kai wrote:
>>Fortunately, from AppleScript 1.10 (Mac OS X version 10.4), a new
>considering/ignoring attribute was added - allowing numeric strings to be
>collated by their numeric value.
>
>Your sort is a bubble sort, which is about the slowest sort known to man.
>Here's a merge sort, which is among the fastest. I posted this a while ago
>but have added the considering attribute kai mentions to get the behavior
>you want.
Both handlers could be made more flexible by putting the considering
attributes round the calls rather than incorporating them into the sort code.
Jon's merge sort isn't quite twice as fast as kai's sort (which I imagine
was posted more to show the attribute use than to provide a heavy-lifting
sort handler). On my machine, kai's handler sorts 1000 random integers in
2.088 seconds, Jon's in 1.138 seconds. But Jon's sort seems to be a
literal translation from C. If it were optimised for AppleScript, it
could be a lot faster. For instance, the latest version of the merge sort
I posted last month in reply to Jon sorts 1000 integers in 0.108 seconds
- only a whisker behind Arthur Knapp's and my Quicksort/insertion sort
combination of a few years ago. (0.096 seconds.)
on mergesort(theList, l, r)
script o
property lst : theList
property extract : missing value
on msort(l, r)
set m1 to (l + r) div 2
set m2 to m1 + 1
if (m1 - l > 1) then
msort(l, m1)
else
set leftVal to item l of my lst
set rightVal to item m1 of my lst
if (rightVal < leftVal) then
set item l of my lst to rightVal
set item m1 of my lst to leftVal
end if
end if
if (r - m2 > 1) then
msort(m2, r)
else if (r > m2) then
set leftVal to item m2 of my lst
set rightVal to item r of my lst
if (rightVal < leftVal) then
set item m2 of my lst to rightVal
set item r of my lst to leftVal
end if
end if
set my extract to items l thru r of my lst
set leftIdx to 1
set leftLen to m2 - l
set rightIdx to leftLen + 1
set extractLen to r - l + 1
set leftVal to beginning of my extract
set rightVal to item rightIdx of my extract
repeat with i from l to r
if (rightVal < leftVal) then
set item i of my lst to rightVal
if (rightIdx < extractLen) then
set rightIdx to rightIdx + 1
set rightVal to item rightIdx of my extract
else
repeat with i from (i + 1) to r
set item i of my lst to item leftIdx of my extract
set leftIdx to leftIdx + 1
end repeat
exit repeat
end if
else
set item i of my lst to leftVal
if (leftIdx < leftLen) then
set leftIdx to leftIdx + 1
set leftVal to item leftIdx of my extract
else
exit repeat
end if
end if
end repeat
end msort
end script
set listLen to (count TheList)
if (listLen > 1) then
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
else
if (l > r) then
set temp to l
set l to r
set r to temp
end if
o's msort(l, r)
end if
end if
return -- nothing
end mergesort
-- Demo:
set l to {}
repeat with i from 1 to 1000
set end of my l to (random number 1000)
end repeat
set t to (GetMilliSec)
mergesort(l, 1, -1) -- Sort items 1 thru -1 of l
l
((GetMilliSec) - t) / 1000
NG
_______________________________________________
Do not post admin requests to the list. They will be ignored.
AppleScript-Users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
Archives: http://lists.apple.com/archives/applescript-users
This email sent to email@hidden