Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!dan
From: dan@Apple.COM (Dan Allen)
Newsgroups: comp.sys.mac.hypercard
Subject: Re: Sorting Containers (HyperTalk Script)
Message-ID: <32682@apple.Apple.COM>
Date: 26 Jun 89 21:14:22 GMT
References: <32656@apple.Apple.COM> <18102@usc.edu>
Distribution: comp.sys.mac.hypercard
Organization: Apple Computer Inc, Cupertino, CA
Lines: 18

In article <18102@usc.edu> kurtzman@pollux.usc.edu (Stephen Kurtzman) writes:
>This is picky, but I suspect that an expression such as "line j of it" is
>not an O(1) operation in HyperTalk. If we assume some reasonable fixed bound
>on line length, then it is probably O(j) since it would have to scan the
>string for the j-1 occurrence of a line break and then copy all of the
>characters up to the jth line break. What this means is, if my suspicion
>is correct and we assume there is an upper limit on line length,
>the script above is actually O(n**3), where n is the number of lines in
>the container.

Good point.  This script could probably be optimized massively, but as
mentioned, it is a short (1 screen) script that sorts lines.  I hope
other people can pull out their Knuth "Sorting and Searching" volumes
and improve on this simple example.  I wrote the script in 10 minutes.
I am sure that hours will prove worthwhile.

Dan Allen
Apple Computer