Re: Sorting a list of records
Re: Sorting a list of records
- Subject: Re: Sorting a list of records
- From: "Nigel Garvey" <email@hidden>
- Date: Tue, 24 Aug 2010 10:20:02 +0100
Gil Dawson wrote on Mon, 23 Aug 2010 15:58:41 -0700:
>The AppleScript 'CustomQsort' algorithm suggested by Adam Bell, Nigel
>Garvey, et al in (http://macscripter.net/viewtopic.php?id=17340) works
>well in my application except that the underlying QuickSort algorithm is
>intrinsically not "stable".
Merge Sort is a stable. I have in fact recently posted a customisable
Merge Sort on the same forum as above:
<http://macscripter.net/viewtopic.php?pid=131165#p131165>
If you want to sort records on a |name| property, the script object
you'd need to pass to the handler would look something like this:
script byName
on isLess(a, b)
(a's |name| < b's |name|)
end isLess
-- These other handlers not used here, but must exist.
on getExtract(a, b)
end getExtract
on mergeMove(a, b)
end mergeMove
on swap(a, b)
end swap
end script
Subsequent sorts on other properties could use child script objects, to
save writing them out in full:
script byAge
property parent : byName
on isLess(a, b)
a's age < b's age
end isLess
end script
With a stable sort, if you sort by |name| and then by age, the records
will be in age order with records of equal age being in name order.
However, if you know that's what you want before you start, it's faster
to do a single, all-in-one sort:
script byAgeThenName
on isLess(a, b)
(a's age < b's age) or (a's age = b's age and a's |name| < b's |name|)
end isLess
-- These other handlers not used here, but must exist.
on getExtract(a, b)
end getExtract
on mergeMove(a, b)
end mergeMove
on swap(a, b)
end swap
end script
It turns out that CustomMergeSort() is slightly faster than CustomQsort
() in cases like this when the extra handlers aren't used. It's because
while the Qsort implementation performs much less moving around than the
Merge Sort one, it does quite a few more comparisons. The extra time
required for the comparisons in the custom versions is enough to give
CustomMergeSort() the edge.
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