1 Zkuste podrobně popsat vlastními slovy postup, jak seřadit:
* 10 hracích karet do ruky při rozdávání
* nastoupenou fotbalovou jedenáctku v dresech, pokud má předstoupit o krok dopředu
seřazená podle čísel na dresech
* 200 písemek podle abecedy, jsou-li k dispozici 4 pomocníci
* lidi stojící ve frontě v úzké chodbě podle data narození (pokud každý může mluvit
jenom se svým sousedem)
2 Zkuste neformálně postihnout podstatu následujícího algoritmu.
procedure s1(A[0..N-1]);
begin
left = 0; right = N - 1; swapped = true;
while (swapped == true)
swapped = false;
for (i = left; i < right; i = i + 1)
if (A[i] > A[i + 1]) then
swap(A[i], A[i + 1]);
swapped = true;
right = right - 1;
for (i = right; i > left; i = i - 1)
if (A[i] < A[i - 1]) then
swap(A[i], A[i - 1]);
swapped = true;
left = left + 1;
end;
3 Porovnejte následující programy xsort a ysort. Jaký koncept mají společný? V
čem se zásadně liší?
procedure xsort A[low,high]:
if low<high then
middle:=round((low+high)/2);
xsort A[low,middle];
xsort A[middle+1,high];
seřaď seřazené posloupnosti A[low,middle] a A [middle+1,high];
procedure ysort A[low,high]:
if low<high then
zvol(pivot);
rozděl A na část prvků menších než pivot A[low,ip-1]
a část větších než pivot A[ip+1,high];
ysort A[low,ip-1];
ysort A[ip+1,high];
spoj do jedné posloupnosti A[low,ip-1], pivot, A[ip+1,high];
Algoritmy mergeSort a quickSort ­ funkcionální varianta:
mergeSort :: [Int]->[Int]
mergeSort[] = []
mergeSort[x] = [x]
mergeSort s = merge (mergeSort u) (mergeSort v)
where (u,v) = splitAt (n 'div' 2) s
n = length s
merge s [] = s
merge [] t = t
merge (x:u)(y:v) = if x <= y then x:merge u (y:v)
else y:merge (x:u) v
quickSort :: [Int]->[Int]
quickSort [] = []
quickSort (p:t) = quickSort lt ++ [p] ++ quickSort gs
where lt = [x | x<-t, x<p]
gs = [x | x<-t, x>=p]
Algoritmy mergeSort a quickSort ­ imperativní varianta:
var A[1..n]:integer;
procedure mergeSort(p,r:integer); procedure quickSort(p,r:integer);
var q:integer; var q:integer;
begin begin
if p<r then if p<r then
q:=round((p+r)/2); q:=part(p,r);
mergeSort(p,q); quickSort(p,q-1);
mergeSort(q+1,p); quickSort(q+1,r)
merge(p,q,r) end;
end;
procedure merge(p,q,r:integer); function part(p,r:integer):integer;
var i,j,k:integer; var i,j,x:integer;
var B[1..n]:integer; begin
begin x:=A[r];
i:=p; j:=q+1; i:=p-1;
for k:=p to r do for j:=1 to r-1 do
if i<=q and (j>r or A[i]<=A[j]) if A[j]>=x then
then i:=i+1;
B[k]:=A[i]; swap(A[i],A[j]);
i:=i+1; swap(A[i+1],A[r]);
else return(i+1);
B[k]:=A[j]; end;
j:=j+1;
for k:=p to r do A[k]:=B[k];
end;
4 Jak vypadají nejvíce (nejméně) příznivá vstupní data pro algoritmus insertsort?
procedure insertsort(A[0..n-1]);
int i, j, temp;
begin
for i: = 1 to n-1 do
temp := A[i];
j := i;
while ((j > 0) and (A[j-1] > temp)) do
A[j] := A[j-1];
j := j-1;
A[j] := temp;
end;
5 Ověřte chování algoritmu s2 na vstupu [4,3,6,5,2,7,1].
1: procedure s2(A[0..n-1]);
2: int i, j, gap, temp;
3: begin
4: gap := trunc(n/2);
5: while (gap > 0) do
6: for i := gap to n-1 do
7: j := i;
8: temp := A[i];
9: while ((j >= gap) and (A[j-gap] > temp)) do
10: A[j] := A[j-gap];
11: j := j-gap;
12: A[j] := temp;
13: if (gap = 2) then gap := 1 else gap := round(gap/2.2);
14: end;
Zkuste neformálně postihnout podstatu algoritmu. V čem je algoritmus podobný
algoritmu insertsort a v čem se liší?
Je algoritmus stabilní?
6 Dojde v chování následujícího algoritmu (Dijkstrův quicksort) k zásadní změně
pokud nahradíme test na řádku č. 8 testem i<j?
1: procedure quicksort(l,r:integer)
2: var i,j,a:integer;
3: begin
4: i:=l; j:=r; a:=prvek(l,r);
5: repeat
6: while A[i]<a do i:=i+1;
7: while A[j]>a do j:=j-1;
8: if i<=j then
9: swap(A[i],A[j]);
10: i:=i+1;j:=j-1;
11: until i>j;
12: if l<j then quicksort(l,j);
13: if i<r then quicksort(i,r);
14: end;
7 Navrhněte nějaké způsoby výběru prvku a (řádek č. 4 v předchozím programu).
Jakou vlastnost má nejvhodnější prvek?
8 Pokud známe uspořádání dvojic (a, b) a (b, c), můžeme něco usoudit i o dvojici
(a, c)? V kterých případech? Uveďte příklady využití v algoritmech řazení.
9 Def: Nechť K je úplně uspořádaná množina tzv. klíčů (např. z N).
Binární halda je binární strom, jehož uzly jsou ohodnoceny prvky K a který splňuje:
1. Délky všech větví se liší nejvýše o 1: mají délku k nebo k - 1 (k - hloubka stromu)
2. Hodnoty uzlů na každé větvi jsou vzestupně (sestupně) uspořádány.
Příklady
___ 15 ___
/ \
14 13 1
/ \ / \ / \
12 7 11 8 4 3
/ \ / \ / \ / \ / \ / \
4 9 6 5 1 10 3 2 5 9 6 7
maximová halda minimová halda
10 Rozhodněte, zda jsou následující stromy binární haldou. Odpověď zdůvodněte.
a) __ 15 __ b) 15 c) 15
/ \ / \ / \
12 13 4 10 12 13
/ \ \ / \ / | \ \
1 3 10 9 8 1 3 5 10
/ \ / / / \ / / \
2 5 6 7 6 3 2 6 8
11 Přepište tuto haldu do pole A[1..n], n=15, podle předpisu:
pro každé 1  i  n
A[i] ___ 15 ___
/ \ / \
A[2i] A[2i+1] 14 13
/ \ / \
12 7 11 8
/ \ / \ / \ / \
4 9 6 5 1 10 3 2
12 Ze dvou maximových hald velikosti n vytvořte jednu velikosti 2n + 1 přidáním
určeného prvku:
a) přidejte 9 e) 5 10 přidejte 9
7 3 ---------> / \ / \ ---------->
4 3 8 2
b) přidejte 5
7 3 --------->
c) přidejte 1 f) 5 10 přidejte 6
7 3 ---------> / \ / \ ---------->
4 3 8 2
d) 5 10 přidejte 11
/ \ / \ ---------->
4 3 8 2
13 Odeberte z následující (maximové) haldy maximum a vytvořte opět (zleva
zarovnanou) haldu:
___ 15 ___
/ \
14 13
/ \ / \
12 7 11 8
/ \ / \ / \ / \
4 9 6 5 1 10 3 2
14 Který algoritmus řazení je nejlepší?
Název Časová složitost
Min Prům Max
bubblesort - řaz. výměnou (n) (n2
) (n2
)
heapsort - řaz. haldou (n  log n) (n  log n) (n  log n)
insertsort - řaz. vkládáním (n) (n2
) (n2
)
mergesort - řaz. slučováním (n  log n) (n  log n) (n  log n)
quicksort - řaz. rozdělováním (n  log n) (n  log n) (n2
)
selectsort - řaz. výběrem (n2
) (n2
) (n2
)