Nech K je lineárne usporiadaná množina (reflexívna, tranzitívna a antisymetrická množina). Nech n je prirodzené číslo, nł 1,

a nech A = (a₁, a₂,..., a_n), a_i Î K pre 1Ł iŁ n, je postupnosť prvkov množiny K.

• k danej vstupnej postupnosti A je potrebné vytvorí
• novú výstupnú postupnosť p(A), ktorá je permutáciou prvkov postupnosti A takou, že platí

Algoritmy triedenia sú vyhodnocované z hľadiska počtu porovnaní a počtu presunov prvkov, ktoré patria do uvažovanej lineárne usporiadanej množiny.

Cyklus pre i je opakovaný (n-1)-krát,

cyklus pre j sa môže opakovať 0 (ak prvok a[i] patrí na koniec už utriedenej postupnosti) až (i-1)-krát (ak prvok a[i] patrí na začiatok), preto počet porovnaní prvkov postupnosti medzi sebou je v najlepšom prípade rovný n-1 a v najhoršom prípade n.(n-1)/2.

Tento algoritmus je typickým predstaviteľom algoritmov založených na rekurzii a na aplikácii metódy delenia problému na podproblémy toho istého typu ale menších rozmerov (metóda sa tiež nazýva rozdeľuj a panuj).

Celý algoritmus je založený na jednoduchom princípe:

rovné ako prvok X a v pravej časti len prvky väčšie alebo rovné ako prvok X. Po tomto rozdelení je evidentné, že prvky, ktoré ležia v ľavej časti poľa, zostanú v tejto časti aj po úplnom utriedení a to isté platí o pravej časti poľa. Na poradí prvkov s rovnakou hodnotou nezáleží, takže aj prípadný výskyt viacerých prvkov s rovnakou hodnotou X nespôsobí problémy. Teraz postačuje utriediť samostatne ľavú a samostatne pravú časť poľa. To sú vlastne dva menšie podproblémy rovnakého typu, ale menšie, čo sa týka počtu prvkov. Na tie aplikujeme podobnú metódu. Ak úsek obsahuje jeden prvok, tak tento úsek je už utriedený a už nie je treba nič robiť.

Popíšeme, ako je možné vhodne poprehadzovať prvky podľa našej potreby. Na to potrebujeme dva pomocné indexy ukazujúce do práve spracovávaného úseku poľa. Index ii začína ľavom okraji úseku a zväčšuje sa, pokiaľ nenájdeme prvok väčší ako X. Ten nepatrí do vytváranej ľavej časti a má sa presunúť niekam vpravo. Podobne s indexom jj postupujeme od pravého okraja úseku smerom doľava, pokiaľ nenájdeme prvý menší prvok ako X. Ten sa má presunúť do ľavej časti. Oba nájdené prvky spolu vymeníme. Potom pokračujeme rovnakým spôsobom v pohybe indexov ii a jj smerom do stredu a vymieňame dovtedy, kým sa oba indexy nestretnú. V tomto okamihu je celý úsek rozdelený na ľavú časť s menšími prvkami ako X a pravú časť s väčšími prvkami. Hranica oboch úsekov je daná polohou indexov ii a jj. časová zložitosť tohoto delenia je lineárna, počet operácií je úmerný počtu prvkov v úseku.

const
  max=100;

type
  info = record
    meno:string;
    x,y:integer;
  end;

  tabulka = record
    pocet:0..max;
    p:array[1..max] of info;
  end;

function CitajRiadok(var t:Text):info;
var
  z:char;
begin
  with Result do begin
    meno:=''; read(t,z);
    while z<>';' do begin
        meno:=meno+z; read(t,z);
    end;
    readln(t,x,y);
  end;
end;

procedure zarad(var tab:tabulka; pp:info);
begin
  with tab do begin
    inc(pocet); p[pocet]:=pp;
  end;
end;

function hladaj(tab:tabulka;  m:string):integer;
begin
  Result:=tab.pocet;
  while (Result>0) and (tab.p[Result].meno<>m) do dec(Result);
end;

var
  tab: tabulka;

Naučíme sa nový typ algoritmu - binárne vyhľadávanie - podobný, ako keď hľadáme v telefónnom zozname:

function hladaj(tab:tabulka;  m:string):integer;
var
  z,k,s:integer;
begin
  z:=1; k:=tab.pocet; s:=1;   {začiatok a koniec intervalu}
  while z<=k do begin
    s:=(z+k) div 2;           {stred intervalu}
    if tab.p[s].meno<m then z:=s+1
    else if tab.p[s].meno>m then k:=s-1
    else z:=k+1;
  end;
  if tab.p[s].meno=m then Hladaj:=s
  else Hladaj:=0;
end;

function hladaj( tab:tabulka; m:string):integer;
var
  z,k,s:integer;
begin
  z:=1; k:=tab.pocet;
  while z<k do begin
    s:=(z+k) div 2;
    if tab.p[s].meno<m then z:=s+1
    else if tab.p[s].meno>m then k:=s-1
    else begin z:=s; k:=s end
  end;
  if (z=k) and (tab.p[z].meno=m) then Hladaj:=z
  else Hladaj:=0;
end;