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)
Zkuste neformálně postihnout podstatu následujícího algoritmu.
function 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;
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];
Porovnejte následující programy mergeSort a quickSort. Jaký koncept mají
společný? V čem se zásadně liší?
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]
Porovnejte následující programy mergeSort a quickSort. Jaký koncept mají
společný? V čem se zásadně liší?
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);
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]) then if A[j]>=x then
B[k]:=A[i]; i:=i+1;
i:=i+1; swap(A[i],A[j]);
else swap(A[i+1],A[r]);
B[k]:=A[j]; return(i+1);
j:=j+1; end;
for k:=p to r do A[k]:=B[k];
end;
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;
Navrhněte nějaké způsoby výběru prvku a (řádek č.4 v předchozím programu). Jakou
vlastnost má nejvhodnější prvek?
Kolik operací provedeme při třídění posloupnosti délky n, pokud budeme porovnávat
každý prvek s každým?
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í.
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
Rozhodě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
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
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
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
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
)