Triedenie ? Sekvencné architektúry
Priame zobrazenie na SA dáva:
- P1: má N ? 1 príkazov, ktoré sa vykonávajú v cykle cez rastúce i, celý program potrebuje O(N2) krokov
- P2: podobne
V nasledujúcom ukázeme lepšiu realizáciu P1 a P2 na SA. Z P2 odvodíme heapsort, zlozitost O(N.log N) krokov. Jadrom je zefektívnenie výpoctu maxima pola y[1 .. m]. Prvky y[1 .. m] dáme do haldy tak, ze y[1] je maximum.
Program skeleton?heapsort
declare
m: integer
initially
m = N
assign
y[m], y[1], m := y[1], y[m], m ? 1
if y[1] = ? max j: 1 ? j ? m:: y[j] ? ? m > 1
? príkazy na permutáciu y[1 .. m] tak, ze y[1] je maximum