program RychleTrideniQuickSort;

uses CRT;{ Unita pro praci s obrazovkou}

const MaxN = 100; {maximalni pocet tridenych cisel}

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

var P: Pole;     {ulozeni tridenych udaju}

    i:integer;

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





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

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

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

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

        i, j: integer;  {posouvane pracovni indexy v poli}

    begin

     i:=Zac; j:=Kon;  k:=P[(Zac+Kon) div 2];

 {za hodnotu X vezmeme pro jednoduchost prostredni prvek ve zkoumanem useku}

         Repeat

           while P[i] < k do i:=i+1;

           while P[j] > k do j:=j-1;

           if   i < j then {vymenit prvky s indexy I a J}

                        begin

                         x:=P[i]; P[i]:=P[j]; P[j]:=x;

                         i:=i+1; j:=j-1;   {posun indexu na dalsi prvky}

                        end

                      else if i = j then {indexy i, j se sesly, oba dva ukazuji na hodnotu k}

                                     begin

                                      i:=i+1; j:=j-1 {posun indexu na dalsi prvky, nutne kvuli ukonceni cyklu}

                                     end

         until i > j;

{usek <Zac,Kon> je rozdelen na useky <Zac,j> a <i,Kon>, ktere zpracujeme rekurzivnim volanim procedury:}

         if Zac < j then QuickSort(P, Zac, j);

         if i < Kon then QuickSort(P, i, Kon);

   end;  {procedure QuickSort}





begin {hlavni program}

clrscr;  {Vymazani obrazovky}

writeln('Zadej N prvku pole, ktere chces setridit:');

writeln('Maximalne vsak ',MaxN, ' prvku.');

write('Pocet prvku:');Readln (N);

writeln('Zadej jednotlive prvky pole:');

for i:=1 to N do begin write(i,'. prvek pole:'); readln(P[i]);end;

writeln;

writeln;



QuickSort(P, 1, N);

writeln('Setridene pole:');

writeln;

for i:=1 to N do   write('  ',P[i]);

repeat until keypressed;



end.