Proč se vůbec řazením zabýváme? Proč chceme posloupnosti dat řadit?
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)
Všechny asociativní řadící algoritmy patří do třídy (n log2 n). Dokážete najít
algoritmus, který jisté typy posloupností uspořádá rychleji, tj. v čase o(n log2 n)?
Na čem je založen princip fungování algoritmu Bubblesort? Jaká je jeho složitost v
nejlepších, průměrných a nejhorších případech? Je tento algoritmus stabilní? Chová se
přirozeně? Je 'in situ' algoritmus?
Na čem je založen princip fungování algoritmu Insertsort? Jaká je jeho složitost v
nejlepších, průměrných a nejhorších případech? Je tento algoritmus stabilní? Chová se
přirozeně? Je 'in situ' algoritmus?
Na čem je založen princip fungování algoritmu Selectsort? Jaká je jeho složitost v
nejlepších, průměrných a nejhorších případech? Je tento algoritmus stabilní? Chová se
přirozeně? Je 'in situ' algoritmus?
Pomocí algoritmu Mergesort seřaďte posloupnost [6,3,8,3,7,3,6,1,4].
Pomocí algoritmu Quicksort seřaďte posloupnost [6,3,8,3,7,3,6,1,4].
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?
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
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
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) 7 3 přidejte 9 e) 5 10 přidejte 9
b) 7 3 přidejte 5 / \ / \
c) 7 3 přidejte 1 4 3 8 2
d) 5 10 přidejte 11 f) 5 10 přidejte 6
/ \ / \ / \ / \
4 3 8 2 4 3 8 2
Vytvořte binární maximovou (zleva zarovnanou) haldu z následujícího pole
[5,9,1,14,7,11,13,4,12,6]
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
Pomocí algoritmu Heapsort seřaďte posloupnost [6,3,8,3,7,3,6,1,4]. Použijte in situ
variantu algoritmu.
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;
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
)
Pokud známe uspořádání dvojic (a, b) a (b, c), můžeme něco usoudit i o dvojici
(a, c)? Ve kterých případech? Uveďte příklady využití v algoritmech řazení.
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;
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;