Re: Fastest Alphabetizer(sorter) for Lists
Re: Fastest Alphabetizer(sorter) for Lists
- Subject: Re: Fastest Alphabetizer(sorter) for Lists
- From: "Arthur J Knapp" <email@hidden>
- Date: Wed, 02 May 2001 10:56:16 -0400
>
Date: Tue, 01 May 2001 20:31:28 -0400
>
Subject: Re: Fastest Alphabetizer(sorter) for Lists
>
From: Jason Bourque <email@hidden>
>
> Here is another way to implement the quicksort handler:
>
> set myList to {20, "2% Milk", "email@hidden"}
>
> SortAsStrings(myList)
>
> myList
>
> -- > {"2% Milk", 20, "email@hidden"}
>
> property qsort_compare : missing value
>
>
Oops, you lost me. What is "missing value"(I forgot this lovely piece when
>
first testing the script you sent me.)
This lovely piece wasn't actually a part of the original script
that I posted. "missing value" is an AppleScript constant. It doesn't
mean anything in particular, in fact, I could have just set qsort_compare
to 0, "", false, or any other unimportant value. It is used by the other
handlers to temporarily hold a handler.
The purpose for the qsort_compare property isn't directly related
to sorting, but to what is nessesary for passing a handler as a parameter
to another handler.
bbb( aaa ) -- > call bbb, passing aaa as a parameter
property handler_property : 0
on aaa()
display dialog "Hello World"
end aaa
on bbb( handler_parameter )
-- Can't treat a local var as a handler:
--
-- handler_parameter() -- > error
-- So set a global var to the local var
--
set handler_property to handler_parameter
-- and then call it
--
handler_property() -- > dialog "Hello World"
end
>
Now I will see if I can unravel the logic of the sort. . .
I appoligze for my cryptic style of scripting. I picked up some
very bad coding habits early in my scripting career, and I've never
really broken free of them.
>
> on CompareAsStrings(a, b)
This is a comparison handler. It takes two values, a and b.
If a ( is less than / should sort before ) b, then a negative
integer is returned. If a ( is greater than / should sort after )
b, then a positive integer is returned. If the two values are
"equivalent" according to the rules of this handler, then zero
is returned.
>
> to SortAsStrings(lst)
This handler is an "interface" to qSort, ie: it sets up some
initial values before qSort goes into action.
>
> set qsort_compare to CompareAsStrings
The following implementation of quicksort uses whatever handler
happens to be inside of the qsort_compare property, so we set
it to CompareAsStrings, the comparison handler that has our "rules"
for comparing things.
>
> qSort(lst, 1, length of lst)
So we call qSort,
>
> set qsort_compare to missing value
and then we reset the property, (it's just good practice to do
this).
>
> end SortAsStrings
>
> to qSort(lst, l, r)
I'm not qualified to explain quicksort. My implementation was
originally inspired by, (though not identical to), an implementation
from the "Tao of AppleScript" book.
>
> set {a, z, v} to {l, r, lst's item ((l + r) div 2)}
>
> repeat until z is less than or equal to a
>
> repeat while qsort_compare(item a of lst, v) < 0
So we call qsort_compare, which is set to the comparison
handler SortAsStrings. Note how:
repeat while ( v1 < v2 )
is analogous to :
repeat while ( qsort_compare( v1, v2 ) < 0 )
Arthur J. Knapp
http://www.stellarvisions.com
mailto:email@hidden
Hey, check out:
http://home.earthlink.net/~eagrant/