Triedenie ? Paralelné architektúry (synchrónne)
zistíme, co sa dá vykonat paralelne
Program P4
assign
? || i: 1 ? i < N ? even(i)::
y[i], y[i + 1] := sort2(y[i], y[i + 1]) ?
? ? || i: 1 ? i < N ? odd(i)::
y[i], y[i + 1] := sort2(y[i], y[i + 1]) ?
O(N) procesormi vykonanie P4 trvá O(N). Nasledujúci program priamo „pocíta“ kroky.
Program P5
declare m: integer
initially k = 0 ? y[0] = ?? ? y[N + 1] = ?
assign
? || i: 1 ? i ? N:: y[i] := min(y[i], y[i + 1]) if (i = k mod 2) ~
max(y[i], y[i ? 1]) if (i ? k mod 2) ?
|| k := k + 1 if k < N