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) ------------------------------------------------------------------