Program UKAZ01A(input,output);
uses CRT;
type WSKAZ= ^STRU;
     STRU = record IM : string[10];
                   WS : WSKAZ;
           end;
var LIST, NOVY, KON : WSKAZ;       {KON pro QUICKSORT}
    CH:char;
Procedure OUTLIST(var FLIST:WSKAZ);
    var H:WSKAZ;
    begin  H:=LIST;
           repeat Writeln(H^.IM);
                  H:=H^.WS
           until H=nil;
    end;
Procedure STRSEL(var FLIST:WSKAZ);
    var FIRST, NEXT, PRE, HLED, POM : WSKAZ;
    begin FIRST:=FLIST;
          FLIST:=nil;
          repeat HLED:=FIRST;
                 NEXT:=FIRST^.WS;
                 POM:=FIRST;
                 repeat if NEXT^.IM>HLED^.IM
                           then begin PRE:=POM;
                                      HLED:=NEXT
                                end;
                        POM:=NEXT;
                        NEXT:=NEXT^.WS
                 until NEXT=nil;
                 if HLED=FIRST then begin POM:=FIRST^.WS;
                                          FIRST^.WS:=LIST;
                                          LIST:=FIRST;
                                          FIRST:=POM
                                    end
                               else begin PRE^.WS:=HLED^.WS;
                                          HLED^.WS:=LIST;
                                          LIST:=HLED;
                                    end
          until FIRST^.WS=nil;
          FIRST^.WS:=LIST;
          LIST:=FIRST
    end;
Procedure QUICKSORT(var ZAC, KON: WSKAZ);
        procedure ROZDEL(var ZAC, KON : WSKAZ);
        var pivot, POM, NEXT : WSKAZ;
        begin pivot := ZAC;
              POM := pivot^.WS;
              NEXT := pivot;
              repeat if POM^.IM < pivot^.IM
                       then begin
                              {hodnota je mensi, strcime pred pivota}
                              {premostime diru vzniklou odstranenim prvku}
                              NEXT^.WS := POM^.WS;
                              {presuneme prvek na spravne misto}
                              POM^.WS := ZAC;
                              ZAC := POM;
                              if POM=KON then KON:=NEXT
                            end
                       else begin {posuneme se na dalsi prvek}
                                  NEXT := POM;
                            end;
                     POM := NEXT^.WS;
              until (POM=nil) or (POM=KON^.WS);
              if ZAC <> pivot then ROZDEL(ZAC, pivot);
              if (pivot <> KON) and (pivot^.WS <> KON) and (pivot^.WS <> nil)
                 then ROZDEL(pivot^.WS, KON);
        end;
begin
        rozdel(ZAC, KON);
end;

begin ClrScr;
      new(LIST);                {tvorba a naplneni prvni polozky}
      with LIST^ do begin Write('Zadej prvni jmeno: '); Readln(IM);
                          WS := nil;
                          KON:=LIST;  {KON pro QUICKSORT}
                   end;
      repeat new(NOVY);          {tvorba a naplneni dalsi polozky}
             with NOVY^ do begin Write('Zadej dalsi jmeno: '); Readln(IM);
                                 WS  := nil;
                          end;
             NOVY^.WS:=LIST;     {pridani dalsi polozky na zacatek seznamu}
             LIST:=NOVY;
             Write('Budes jeste zadavat vstupni jmeno A/N? ');Readln(CH);
      until not (CH in ['a','A','y','Y']);

      {Je vytvoren tento linearni dynamicky seznam LIST}
      {v opacnem poradi, nez jak bylo zadavano (prvni je posledni}
      Writeln('Tisk vstupnich dat (v opacnem poradi, nez bylo nacitano):');
      OUTLIST(LIST);

      {Seradime seznam metodou primeho vyberu}
      STRSEL(LIST);}

      {a vytiskneme serazeny seznam}
      Writeln;
      Writeln('Tisk vzestupne serazenych hodnot seznamu metodou STRSEL:');
      OUTLIST(LIST);}

      {Obdobne jej seradime metodou QUICK}
      QUICKSORT(LIST,KON);
      Writeln('Tisk vzestupne serazenych hodnot seznamu metodou QUICK:');
      OUTLIST(LIST);
end.