Re: Sort items in a list without OSAXen
Re: Sort items in a list without OSAXen
- Subject: Re: Sort items in a list without OSAXen
- From: Arthur J Knapp <email@hidden>
- Date: Sun, 02 Sep 2001 14:20:25 -0400
>
Date: Sat, 1 Sep 2001 23:54:28 -0500
>
From: "Joseph A. Weaks" <email@hidden>
>
Subject: Sort items in a list without OSAXen
>
I have a variable that contains random numbers in a list, say
>
{1,2,3,4}, and I need the sum of the highest three.
>
I don't want to use an OSAX 'sort' command for portability reasons.
How fortuatious that this post has come up... :)
I have just created a new vanilla AppleScript implementation of
insertion sort, with a few AppleScript tricks thrown in...
-- ??? Attention math people: is there a better number to use here ???
-- This is the "most negative number" that I can seem to generate.
--
property kLeastNumber : -1.0E+18
property kNotANumber : ""
on SortedNumbers(lst) -- returns new list, (does not work in-place)
-- prepend sentinal
--
set lst to {kLeastNumber} & lst
--
-- also prevents modifying original list, which is important because
-- we will be using the class-delete method to create new versions
-- of lst.
-- This is basically insertion sort. We start at 3 because item 1
-- is the sentinal, so we sort from 3 to 2, 4 to 2, 5 to 2, etc...
--
repeat with i from 3 to lst's length
-- This test tells us if we need to do anything at all with
-- item i, (becuase items from (i - 1) and back are already
-- sorted, so we only need to move item i if it sorts before
-- item (i - 1)).
--
if lst's item i < lst's item (i - 1) then
-- We grab the value that is being moved, v = lst's item i.
-- We assign lst's item i to any non-number, (class-delete).
-- Since we already know that item i < item (i - 1), we
-- set i to i - 2.
--
set {v, lst's item i, i} to {lst's item i, kNotANumber, i - 2}
-- We want to end up with i just before where v is to be
-- inserted.
--
repeat while v < lst's item i
set i to i - 1
end repeat
-- Having created a new lst thru concatenation, we then
-- class-delete the original position of v by getting
-- just numbers, (we previously set lst's item i to
-- kNotANumber).
--
set lst to ((lst's items 1 thru i) & v & ,
(lst's items (i + 1) thru -1))'s numbers
end if
end repeat
return lst's rest -- remove the sentinal
end SortedNumbers
I'm afraid my comments aren't as good as they should be...
One of the things that bothers me about the SortedNumbers handler
is that you can't directly modify the passed list, so I have created
a separete version that works with "a ref to" values:
set myList to {6, 3, 8, 2, 5, 1, 7, 8, 3, 9, 2, 5, 0, 1, 5, 7}
set listReference to a reference to myList
SortedRefNumbers(listReference)
myList --> {0, 1, 1, 2, 2, 3, 3, 5, 5, 5, 6, 7, 7, 8, 8, 9}
on SortedRefNumbers(refList)
tell refList
set beginning to kLeastNumber
repeat with i from 3 to length
if item i < item (i - 1) then
set {v, item i, i} to {item i, kNotANumber, i - 2}
repeat while v < item i
set i to i - 1
end repeat
set contents to (items 1 thru i & v & ,
items (i + 1) thru -1)'s numbers
end if
end repeat
set contents to rest
end tell
end SortedRefNumbers
Because of the class-delete method, the handler has to be written
for each type of sortable-items list, ie: strings, dates, etc. For
strings, you can use this:
property kLeastString : ASCII character 0
property kNotAString : 0
on SortedStrings(lst)
set lst to {kLeastString} & lst
repeat with i from 3 to lst's length
if lst's item i < lst's item (i - 1) then
set {v, lst's item i, i} to {lst's item i, kNotAString, i - 2}
repeat while v < lst's item i
set i to i - 1
end repeat
set lst to ((lst's items 1 thru i) & v & ,
(lst's items (i + 1) thru -1))'s strings
end if
end repeat
return lst's rest
end SortedStrings
My initial testing has shown these handlers to be much faster
than previously posted vanilla AppleScript sorting methods, (even
than my own implementation of quicksort). I find this exciting,
and when I have completed a more rigourous test, I will post my
results.
Arthur J. Knapp
http://www.stellarvisions.com
mailto:email@hidden
Hey, check out:
http://MacScripter.net