Program QuikSort_bez_rekurze;

const MaxN = 100;        {maximalni pocet tridenych cisel}

MaxNdiv2 = 50;  {= MaxN div 2 (velikost zasobniku)}

type Pole = array[1..MaxN] of integer;   {tridena cisla}

var P: Pole;        {ulozeni tridenych udaju}

N: 1..MaxN;    {pocet prvku v poli P}

Zasob: array[1..MaxNdiv2] of

record Zac, Kon: integer end;   {zasobnik useku cekajicich na zpracovani}

Vrchol: 0..MaxN;                      {vrchol zasobniku}

I: integer;

procedure Quicksort2(var P:Pole; Zac,Kon:integer);

{setridi v poli P usek od indexu Zac do indexu Kon}

var X: integer;   {hodnota pro rozdeleni na useky}

    Q: integer;   {pomocne pro vymenu prvku v poli}

    Z,K: integer; {zacatek a konec zkoumaneho useku}

    I,J: integer; {posouvane pracovni indexy v poli}

 begin

    Zasob[1].Zac:=Zac;   Zasob[1].Kon:=Kon;  Vrchol:=1;

      {cely trideny usek vlozen do zasobniku}

    while Vrchol>0 do  {zasobnik je neprazdny}

     begin   Z:=Zasob[Vrchol].Zac; K:=Zasob[Vrchol].Kon;

             Vrchol:=Vrchol-1;    {odebran jeden usek ze zasobniku}

             I:=Z; J:=K;    X:=P[(I+J) div 2];

                           {za hodnotu X vezmeme pro jednoduchost

                         prostredni prvek ve zkoumanem useku}

             repeat

                while P[I] < X do I:=I+1;

                while P[J] > X do J:=J-1;

                if I < J then

                        begin

                         Q:=P[I]; P[I]:=P[J]; P[J]:=Q;

                          {vymenit prvky s indexy I a J}

                         I:=I+1; J:=J-1;   {posun indexu na dalsi prvky}

                        end

                         else if I = J then

                      {indexy I a J se sesly, oba dva ukazuji na hodnotu X}

                          begin I:=I+1; J:=J-1 {posun indexu na dalsi prvky

                                         - nutne kvuli ukonceni cyklu}

                          end

             until I > J;

                {usek <Z,K> je rozdelen na useky <Z,J> a <I,K>,

                 ktere vlozime do zasobniku k dalsimu zpracovani:}

            if Z < J then

                        begin

                      Vrchol:=Vrchol+1;  Zasob[Vrchol].Zac:=Z;

                      Zasob[Vrchol].Kon:=J

                        end;

            if I < K then

                     begin

                    Vrchol:=Vrchol+1; Zasob[Vrchol].Zac:=I;

                    Zasob[Vrchol].Kon:=K

                     end

     end {end while Vrchol>0 }

 end;        {procedure Quicksort2}

begin  {hlavni program}

write('Pocet tridenych cisel: ');

readln(N);writeln('Zadani posloupnosti tridenych cisel:');

for I:=1 to N do read(P[I]);

Quicksort2(P,1,N);

writeln('Setridena cisla:');

for I:=1 to N do write(P[I]:5);writeln

end.