Re: Sorting? [sorted]
Re: Sorting? [sorted]
- Subject: Re: Sorting? [sorted]
- From: Ron Hunsinger <email@hidden>
- Date: Sun, 15 Sep 2002 18:05:54 -0700
At 12:01 PM +0100 9/13/02, has wrote:
Mine mashes the text as well; it just does it in a different place. In
fact, it's not even optimised for this; if you count the number of times a
value is mashed, it's far more than the algorithm actually requires. But I
was really just trying to demonstrate how to create a more flexible sort
routine: describing ways to optimise it would be a sizeable essay in
itself.;) [Which in turn would have to start by finding a replacement to
the cruddy O(n^2) sorting algorithm provided... and so on.] The usual use
for mine would be sorting lists or records on a given item (which it makes
trivially easy), but I reckoned it'd be good enough to solve this problem
too so I posted it.
I almost replied earlier about the complexity of your posted code,
but didn't because:
a) I realized your focus was on how to adapt an arbitrary sort
algorithm (by using callbacks), rather than on any particular
sort algorithm, and
b) I noticed you mention that you don't actually use this algorithm
to sort with, preferring your own optimized QuickSort.
However, now that you've specifically mentioned the complexity, I
feel compelled to point out that the posted algorithm is actually
O(N^3), not O(N^2).
The basic algorithm was:
on ASCIISort(myList)
set indexList to {}
set sortedList to {}
repeat (number of items in myList) times
set lowItem to ""
repeat with i from 1 to (number of items in myList)
if i is not in indexList then
set thisItem to item i of myList as text
if lowItem is "" then
set lowItem to thisItem
set lowItemIndex to i
else if isLessThan(thisItem, lowItem) then -- CHANGED!!!
set lowItem to thisItem
set lowItemIndex to i
end if
end if
end repeat
set end of sortedList to lowItem
set end of indexList to lowItemIndex
end repeat
return sortedList
end ASCIISort
I draw your attention to the line:
if i is not in indexList then
which is O(N) all by itself, and is executed N^2 times.
It's true that this sort does only O(N^2) compares (and only O(N^2)
value mashings), but for large N those aren't where it will be
spending most of its time. For large N, the time spent testing
whether i is in indexList will utterly swamp everything else.
-Ron Hunsinger
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.