[comp.lang.pascal] Iterative QuickSort TP source

ZCCBJSB%EB0UB011.BITNET@cunyvm.cuny.edu (Josep Sau B.) (11/14/90)

>...'cause I don't have time to dig through
>the library for a qwikSort any time soon *sigh*...

For this poor boy, and for all of you that don't know QuickSort
(really you don't ???), here it is a 'generic' QuickSort:

--- This is the top --- Cut here ------------------------------------
TYPE
  KEY      = STRING;  (* Or any other key to sort on *)
  KEYREF   = LONGINT; (* Or POINTER or any other reference
                         to Nth Element *)
  KEYCOUNT = LONGINT; (* Number of active elements in ARRAY,
                         DIRECT ACCESS FILE, ... *)
  KEYLIST  = ARRAY(.1..MANY.) OF KEY;
                      (* direct access structure containing keys *)

PROCEDURE Swap (VAR a,b : KEY);
   VAR c : KEY;
   BEGIN
      c := a;
      a := b;
      b := c;
   END;

FUNCTION Less (a,b :KEY): BOOLEAN;
      (* TRUE IF a < b,
         Modify this to feet comparison criteria to your needs *)
   BEGIN
      Less := a < b;
   END;

PROCEDURE IterativeQuickSort (VAR List :KEYLIST; q :KEYCOUNT);
      (*
         Iterative QuickSort - No Stack Overflow
         -- according to N.Wirth
         'Algorithms + Data structures = Programs'
      *)
   CONST
      SPMAX=32;   (* Succ(log2(MaxLongInt)) *)
   VAR
      i,j,iz,de : KEYREF;
      Pivot : KEY;
      sp : 0..SPMAX;
      Stack : ARRAY (.1..SPMAX.) OF RECORD
         iz, de : KEYREF;
      END;
   BEGIN
      IF q > 1 THEN BEGIN
         sp:=1;
         Stack(.sp.).iz:=1;
         Stack(.sp.).de:=q;
         REPEAT
            iz:=Stack(.sp.).iz;
            de:=Stack(.sp.).de;
            DEC(sp);
            REPEAT
               i:=iz;
               j:=de;
               Pivot :=List(.(iz+de) DIV 2.);
               REPEAT
                  WHILE Less(List(.i.),Pivot) DO INC(i);
                  WHILE Less(Pivot, List(.j.)) DO DEC(j);
                  IF i<=j THEN BEGIN
                     Swap(List(.i.),List(.j.));
                     INC(i);
                     DEC(j);
                  END;
               UNTIL i > j;
               IF j -iz < de -i THEN BEGIN
                  IF i < de THEN BEGIN
                     INC(sp);
                     Stack(.sp.).iz:=i;
                     Stack(.sp.).de:=de;
                  END;
                  de:=j;
               END
               ELSE BEGIN
                  IF iz < j THEN BEGIN
                     INC(sp);
                     Stack(.sp.).iz:=iz;
                     Stack(.sp.).de:=j;
                  END;
                  iz:=i;
               END;
            UNTIL iz >= de;
         UNTIL sp = 0;
      END;
   END;
---this is the end---- Cut here ------------------------------------


--Josep Sau B. <ZCCBJSB@EB0UB011>
------------------------------------------------------------------
'Every science needs the right words to be expressed the right way'
           Raimundus Lulius (Catalan philosopher)
------------------------------------------------------------------