program K_ty_nejmensi;
{Nalezeni K-teho nejmensiho prvku metodou zalozenou
 na modifikaci tridiciho algoritmus Quicksort}

const MaxN = 100;     {maximalni pocet zpracovavanych cisel}
type  Pole = array[1..MaxN] of integer;      {ulozeni cisel}

var P: Pole;     {ulozeni tridenych udaju}
    N: 1..MaxN;  {pocet prvku v poli P}
    I,K: integer;

function NaleztKty(var P:Pole; Zac,Kon,K:integer):integer;
{v poli celych cisel P v useku od indexu Zac do indexu Kon
vyhleda K-te nejmensi cislo a vrati ho jako funkcni hodnotu}
var X: integer;     {hodnota pro rozdeleni na useky}
    Q: integer;     {pomocne pro vymenu prvku v poli}
    I,J: integer;   {posouvane pracovni indexy v poli}
begin
  while Zac < Kon do
    begin
    X:=P[K];        {jedna mozna volba, lze i jinak}
    I:=Zac;
    J:=Kon;
    repeat
      while P[I] < X do I:=I+1;
      while P[J] > X do J:=J-1;
      if I < J then       {vymenit prvky s indexy I a J}
        begin
        Q:=P[I]; P[I]:=P[J]; P[J]:=Q;
        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 <Zac,Kon> je rozdelen na useky <Zac,J> a <I,Kon>}
    if K < I then Kon:=J; {dal budeme hledat v levem useku}
    if K > J then Zac:=I; {dal budeme hledat v pravem useku}
    end;
    NaleztKty:=P[K]
end;  {function NaleztKty}

begin  {hlavni program}
write('Pocet zpracovavanych cisel: ');
readln(N);
writeln('Zadani posloupnosti zpracovavanych cisel:');
for I:=1 to N do read(P[I]);
write('Kolikaty prvek nalezt?: ');
readln(K);
writeln('Nalezen ', K, '-ty nejmensi prvek: ',
        NaleztKty(P,1,N,K));
writeln
end.