program K_nejvetsich;
{Nalezeni K nejmejvetsich prvku metodou zalozenou
 na modifikaci tridiciho algoritmus Quicksort}
uses crt;

const MaxN = 1000;     {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}
    pom,I,K: integer;
    s:text;

function porovnej(a,b:integer):char;
var z:char;
begin
if a=b then porovnej:='='  {aby tutez kostku Bynari nezkousel davat na 2 misky najednou:-) }
else begin
  writeln('poloz na vahy kostku cislo ',a,' a kostku cislo ',b);
  writeln('jak se naklonily vahy ? ( <, >, = )');
  z:=readkey; porovnej:=z;
end end;

procedure NaleztKty(var P:Pole; Zac,Kon,K:integer);
{v poli celych cisel P v useku od indexu Zac do indexu Kon
vyhleda K-te nejmensi cislo }
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 porovnej(P[I],X)='>' do I:=I+1;
      while porovnej(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  {oba indexy 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;   {mame k-ty nejvetsi prvek a pred nim jsou jen prvky >= }

  writeln('Nalezeno ', K, ' nejvetsich prvku: ');
  for i:=1 to k do write(P[i],',');
  writeln;
end;

begin  {hlavni program}
clrscr;
write('Pocet kostek: '); readln(N);
for I:=1 to N do P[I]:=I;   {nezname vahy cisel, diktujeme jen indexy !!!}
write('Kolik nejvetsich nalezt?: '); readln(K);
NaleztKty(P,1,N,K);
end.