{ programova jednotka demonstrujici } { nerekursivni implementace algoritmu quicksortu} unit nquick; interface const Max = 100; {maximalni velikost trideneho pole} type keytype = integer; item = record key : keytype; { dalsi polozky } end; index = 1..Max; index0 = 0..Max; pole = array [index0] of item; tab = record A : pole; { v poli A[1] ... A[D] tridene pole } D : index; { velikost pole } end; procedure nquick1(var T:tab); { nerekursivni implementace quicksortu} {pomocne procedury} procedure precti(var F:text; var T:tab); { cte z textoveho souboru tabulku T } { predpoklada, ze v nem je na kazde radce prave jedno cislo } procedure vypis(var F:text; T:tab); { vypisuje tabulku T do souboru F } implementation procedure nquick1(var T:tab); const Vmax = 20; {max vyska zasobniku} type usek = record G, { zacatek a } H : index; { konec useku } end; zas = record stack : array [1..Vmax] of usek; V : 0..Vmax; { vyska zasobniku } end; var I,J,K,L : index; W : item; X : keytype; Z : zas; {zasobnik} begin {of nquick1} with T,Z do begin {inicializace - cely interval do zasobniku} V:=1; stack[1].G:=1; stack[1].H:=D; repeat {zasovnik neprazdny - V>0} {vyzvednu usek (K,L) } K:=stack[V].G; L:=stack[V].H; V:=V-1; repeat {zpracuj usek (K,L)} I:=K; J:=L; X:=A[(K+L) div 2].key; repeat {rozdeleni useku (K,L)} while A[I].key < X do I:=I+1; while X < A[J].key do J:=J-1; if I<=J then begin W:=A[I]; A[I]:=A[J]; A[J]:=W; I:=I+1; J:=J-1; end; until I>J; {usek (K,L) rozdelen} if I=L; {vyzvednuty usek (K,L) zpracovan} until V=0 ; {zasobnik je prazdny} end {of with} end {of Nquick}; procedure precti(var F:text; var T:tab); { vstupuji cisla tabulky T vzdy jedno na radce, nekontroluje se je-li jich moc } var I:index0; begin with T do begin I:=0; while not eof(F) do begin I:=I+1; readln(F,A[I].key); end; D:=I; end; end; procedure vypis(var F:text; T:tab); const L = 10; { pocet cisel na radce } FI = 5; { format vystupu } var I,K : index; PD : integer; { pocet cisel, ktere maji jeste vystoupit } begin with T do begin PD:=D; I:=1; while PD>=L do begin {cisel na plnou radku} for K:=I to I+L do write(F,A[K].key:FI); writeln(F); PD:=PD-L; { L cisel vystoupilo } I:=I+L; end; if I<=D then begin {jeste maji vystoupit cisla A[I]...A[D]} for K:=I to D do write(F,A[K].key:FI); writeln(F); end; end {of with } end; end.