Re: Sorting? [sorted]
Re: Sorting? [sorted]
- Subject: Re: Sorting? [sorted]
- From: has <email@hidden>
- Date: Mon, 16 Sep 2002 12:02:41 +0100
Ron Hunsinger wrote:
>
>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
Yup.
>
b) I noticed you mention that you don't actually use this algorithm
>
to sort with, preferring your own optimized QuickSort.
Not sure what you mean? The algorithm I used in this thread was the
GuideBook one (though I removed some of the verbosity so maybe it looks a
little different). Or did you mean the tableLib sort (which is a heavily
modified quicksort) that I mentioned later?
>
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).
Hey, I did say it was junk, didn't I? ;)
Actually, it must be at least O(N^4) - if you also count that retrieving an
item in an AS list is O(N), not O(1) [1]. [2][3]
AppleScript makes it very difficult at times to produce good pedagogical
code that's worth a damn, and that ASCIISort() thing was neither. It
would've been far simpler to have pointed the OP to an existing quicksort
library which supported callbacks and said "just use that", but alas I
don't know of any (note: I think Serge's qSort library uses callbacks, but
only internally). All this trouble must be why other languages ship with
built-in sort functions to start with.;)
Cheers,
has
[1] unless you want to mess about with 'my' keywords or references and all
that nonsense...
[2] What's even more confusing with an interpreted language like AS is that
some of that N is in the user's interpreted code, and some is in the
underlying machine code. Often the latter isn't obvious to the eye. Also,
if you've gotta have O(N) somewhere, it's usually best if it's at the
machine code level, where it's nice and fast, than at the AS level, where
it isn't. (Just imagine if you had to iterate across the list yourself to
check it didn't contain a given value.;)
[3] Anyway, I just spotted the two nested loops and concluded O(N^2); I
didn't even bother to work out the factors introduced by the underlying
language. Beyond O(N^2), who cares anymore? ;)
--
http://www.barple.pwp.blueyonder.co.uk -- The Little Page of AppleScripts
_______________________________________________
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.