Re: how to do a proper alphabetical sort?
Re: how to do a proper alphabetical sort?
- Subject: Re: how to do a proper alphabetical sort?
- From: "Nigel Garvey" <email@hidden>
- Date: Fri, 9 Mar 2007 22:39:08 +0000
Jon Pugh wrote on Thu, 8 Mar 2007 18:33:34 -0800:
>At 3:42 PM -0800 3/8/07, Patrik B. wrote:
>>I am looking for a library or method that does an alphabetical sort?
>I just "wrote" something like this for my own sorting needs.
>
>Actually, I took the pseudocode from the Wikipedia and made it work in
>AppleScript.
>
>It's the mergesort <http://en.wikipedia.org/wiki/Mergesort>:
Coincidentally, I did the very same thing a couple of weeks ago, but
reworked it for "in place" operation. (It sorts the actual list passed to
it rather than returning a sorted copy.) Instead of creating left and
right lists at each recursion level and shaving bits off while merging
them (which produces yet more lists), it makes one copy of each entire
section and uses left and right pointers to merge the items back into the
original list. Not quite as fast as the qsort that Arthur Knapp and I
wrote a few years ago, but not bad.
on mergeSort(theList, l, r)
script o
property mainList : theList
property extract : missing value -- For extracts from the list.
-- Recursive subhandler.
on msort(l, r)
-- Firstly, sort the left and right halves of this section.
set m to (l + r) div 2
if (m > l) then msort(l, m)
if (r > m + 1) then msort(m + 1, r)
-- The left and right halves are now sorted. Extract a copy of
this whole section.
set o's extract to items l thru r of o's mainList
-- Now merge the two halves of the extract back to the original list.
set j to 1 -- Left half index.
set leftLen to m - l + 1 -- Left half length (to the middle of
the extract).
set k to leftLen + 1 -- Right half index.
set extractLen to r - l + 1 -- Extract length.
set leftVal to item j of o's extract
set rightVal to item k of o's extract
repeat with i from l to r -- 'i' indexes the original list.
if (rightVal < leftVal) then -- The current right value's less
than the current left one.
-- Assign it to this slot in the original list.
set item i of o's mainList to rightVal
if (k < extractLen) then
-- If there are more values in the right half, get the next
one.
set k to k + 1
set rightVal to item k of o's extract
else
-- Otherwise dump the remaining left values to the original
list and exit this level.
repeat with i from (i + 1) to r
set item i of o's mainList to item j of o's extract
set j to j + 1
end repeat
exit repeat
end if
else -- The current left value's less than or equal to the
current right one.
-- Assign it to this slot in the original list.
set item i of o's mainList to leftVal
if (j < leftLen) then
-- If there are more values in the left half, get the next one.
set j to j + 1
set leftVal to item j of o's extract
else
-- Otherwise exit this recursion level. The remaining right
values were
-- already OK in the original list when the extract was taken.
exit repeat
end if
end if
end repeat
end msort
end script
-- Sort out the parameters for the recursive subhandler.
set listLen to (count theList)
if (listLen > 1) then
-- Translate negative indices.
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
-- No point in sorting just one item.
else
-- Transpose transposed indices.
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
mergeSort(l, 1, -1) -- Sort items 1 thru -1 of l.
l
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