Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!ucsd!usc!pollux.usc.edu!kurtzman
From: kurtzman@pollux.usc.edu (Stephen Kurtzman)
Newsgroups: comp.sys.mac.hypercard
Subject: Re: Sorting Containers (HyperTalk Script)
Message-ID: <18102@usc.edu>
Date: 26 Jun 89 07:36:36 GMT
References: <32656@apple.Apple.COM>
Sender: news@usc.edu
Reply-To: kurtzman@pollux.usc.edu (Stephen Kurtzman)
Distribution: comp.sys.mac.hypercard
Organization: University of Southern California, Los Angeles, CA
Lines: 52

In article <32656@apple.Apple.COM> dan@Apple.COM (Dan Allen) writes:

>Here is a HyperTalk script that uses the selection sort method of sorting.
>Selection sorting is an algorithm of order n squared, however, for the
>average random cases where n < 1000, selection sorting often performs closer
>to n log n, so it is not bad for small sort jobs.  Quicksort or Heapsort
>would be better for large n, but this is so simple...

>This script is a function.  For example, if you wanted to sort field 1
>of the current card, you could say:

>	put sortContainer(field 1) into field 1

>Here is the actual script:

>function sortContainer anyContainer -- selection sort
>  get anyContainer
>  put the number of lines of it into numLines
>  repeat with i = 1 to numLines - 1
>    put i into k
>    put line i of it into x
>    repeat with j = i+1 to numLines
>      if line j of it < x then
>        put j into k
>        put line j of it into x
>      end if
>    end repeat
>    put line i of it into line k of it
>    put x into line i of it
>  end repeat
>  return it
>end sortContainer

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.

Like I said, it was a picky thing. It shouldn't stop anyone from using
the script. Thanks to Dan for posting it.

A point the script supports, which Dan may or may not have been trying to
make, is that it is easy to quickly put together some very functions useful
functions in HyperTalk. The sortContainer script is a great example. It
probably took Dan a couple of minutes because HyperTalk has simple expressions
to access bits and pieces (actually lines, words, and chars) of containers.
In other words, there's little reason wait around for someone to write an
XCMD for a function that can be implemented very quickly in HyperTalk.