Path: utzoo!attcan!uunet!mitel!sce!scs!spl1!gargoyle!tank!ncar!ames!apple!usc!ucsd!sdcc6!sdacs!wade
From: wade@sdacs.ucsd.EDU (Wade Blomgren)
Newsgroups: comp.sys.mac.hypercard
Subject: Re: Sorting Containers (HyperTalk Script)
Summary: Quicksort example
Message-ID: <105@sdacs.ucsd.EDU>
Date: 3 Jul 89 22:41:55 GMT
References: <15027.24ACEB9A@cmhgate.FIDONET.ORG> <32831@apple.Apple.COM>
Organization: UCSD Academic Computing Services
Lines: 59


Here is the Quicksort algorithm from Wirth translated into HyperTalk.
It seems to work pretty well.  When run against the Selection sort
posted previously (by Dan Allen), it is competitive for N < 30 (sometimes
slower, sometimes faster depending on the initial state of the container),
but increasingly faster for larger N.  It sorted 200 more or less
random lines in about 1/5 the time.  You are still probably better
off with an XCMD or XFCN sort routine for large N, due to the inherent 
overhead of HyperTalk, but this is a workable solution for some situations.

Wade Blomgren
UC San Diego
wade@sdacs.ucsd.edu

-------------cut here--------------
This is a translation of an algorithm, not a software release for any
particular purpose or recipient.  Use at your own risk. No warranty 
is expressed or implied.

function quickSort anyContainer
  get anyContainer
  put 1 into s
  put 1 into item 1 of line s of stack
  put the number of lines of it into item 2 of line s of stack
  repeat until s = 0
    put item 1 of line s of stack into l
    put item 2 of line s of stack into r
    subtract 1 from s
    repeat until l >= r
      put l into i
      put r into j
      put line ((l+r) div 2) of it into x
      repeat until i > j
        repeat while line i of it < x
          add 1 to i
        end repeat
        repeat while x < line j of it
          subtract 1 from j
        end repeat
        if i <= j then
          put line i of it into w
          put line j of it into line i of it
          put w into line j of it
          add 1 to i
          subtract 1 from j
        end if
      end repeat
      if i < r then
        add 1 to s
        put i into item 1 of line s of stack
        put r into item 2 of line s of stack
      end if
      put j into r
    end repeat
  end repeat
  return it
end quickSort

-------------cut here--------------