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: Nigel Garvey <email@hidden>
- Date: Tue, 18 Sep 2001 23:11:28 +0100
A couple of weeks ago, just before I went on holiday, Arthur J Knapp
wrote:
>
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
Here's a souvenir version I brought back from Ireland :-)
on SortedNumbers(lst) -- returns new list, (does not work in-place)
-- This version uses a 'from/to/exit if' repeat, which is
-- slightly faster than the original 'while'.
-- Also, as this form of repeat stops at the sentinal
-- anyway if it doesn't 'exit', the sentinal can have
-- any value at all - as long as it's a number.
set lst to 37 & lst
repeat with i from 3 to lst's length
if lst's item i < lst's item (i - 1) then
set v to lst's item i
set lst's item i to missing value
repeat with j from i - 2 to 1 by -1
if v is not less than lst's item j then exit repeat
end repeat
-- Only extract 'numbers' from the part of the list
-- where the non-number was inserted.
set lst to (lst's items 1 thru j) & v & ,
(lst's numbers (j + 1) thru -1)
end if
end repeat
return lst's rest -- remove the sentinal
end SortedNumbers
SortedNumbers({6, 3, 8, 2, 5, 1, 7, 8, 3, 9, 2, 5, 0, 1, 5, 7, -4000,
-91275483})
--> {-91275483, -4000, 0, 1, 1, 2, 2, 3, 3, 5, 5, 5, 6, 7, 7, 8, 8, 9}
Instead of giving the sentinal a hard value, you could duplicate the
first (say) item in the list:
set lst to ((lst's first item) as list) & lst
This works with any class of item, so you only have to change 'numbers'
to 'text' or 'dates' when adapting the handler to sort lists of these.
(The assumption is, of course, that all the items in a list are of the
same type.)
>
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)
[etc.]
This doesn't directly modify the passed list as claimed. It directly
modifies the *variable* referred to by the passed reference.
SortedRefNumbers() still churns out the same set of intermediate lists,
setting myList to each of them in turn.
NG