Vyhledávání
výběr
prvků daných vlastností v dané posloupnosti hodnot
v poli,
souboru, jiných strukturách (stromy, tabulky,...)
· lineární - v
nesetříděné posloupnosti - postupné prohledávání (učebnice) - složitost n
· binární - v setříděné
posloupnosti - půlením (slovník) - složitost log2n
· (interpolační -
v setříděné posloupnosti se znalostí pravděpodobnosti rozložení
jednotlivých hodnot (interpolační předpokládá rovnoměrné rozložení hodnot, ale
může být i jinak) - složitost log2log2n)
Lineární
Vstupy
Max maximální počet prvků pole
A pole prvků s indexy 1..Max
V(X) funkce typu boolean (daná vlastnost)
parame
M,N krajní indexy prohledávaného úseku pole
Pozn.:
definice
vlastnosti V(X) - globální nebo lokální funkce typu boolean, parametr X je
téhož typu jako prvek pole A
pole
jako parametr - i pro vstup raději volané odkazem
typ
POLE deklarovaný v deklaraci typů
Deklarace:
const
Max = 50;
type
TypPrvku : integer; {na typu prvku pole nezáleží, podle potřeby}
POLE: array[1..MAX]
of TypPrvku;
IPOLE: array[1..MAX]
of integer;
function
V(X:TypPrvku): boolean;
begin
V:=odd(X)
end;
Algoritmy
První vyhledá
index prvního prvku s vlastností V v úseku M,N daného pole
Poslední vyhledá index posledního prvku s vlastností V
v úseku M,N daného pole
Všechny vyhledá
indexy všech prvků s vlastností V v úseku M,N daného pole
Algoritmus
První
Výstup:
I index prvního výskytu prvku s
vlastností V v úseku M..N pole A (I=0 neexistuje takový prvek)
procedure
PRVNI(A:POLE;M,N:integer; var
I:integer);
begin
I:=M-1;
repeat
I:=I+1
until
V(A[I]) or (I=N);
if
not V(A[I]) then I:=0
end;
Algoritmus
Poslední
Výstup:
I index posledního výskytu prvku s
vlastností V v úseku M..N pole A (I=0 neexistuje takový prvek)
procedure
POSLEDNI(A:POLE;M,N:integer; var
I:integer);
begin
I:=M+1;
repeat
I:=I-1
until
V(A[I]) or (I=M);
if
not V(A[I]) then I:=0
end;
Algoritmus
Všechny
Výstup:
K počet prvků dané vlastnosti
B indexy prvků pole A s vlastností V
procedure
VSECHNY(M,N:integer; var
A:POLE; var K:integer; var B:IPOLE);
var
I:integer;
begin
K:=0;
for
I:=M to N do
if
V(A[I]) then begin K:=K+1;B[K]:=I end
end;
Binární
vyhledávání
půlením
v uspořádané posloupnosti
vlastnost
musí být založena na uspořádání (tj. nelze například sudost, lichost, většinou
budeme testovat rovnost)
procedure BINARNI_VYBER
(M,N:integer; var
A:POLE;C:TypPrvku; var
K:integer);
begin
K:=(M+N) div
2;
while
(C<>A[K]) and (M<=N)
do
begin
if
C>A[K] then M:=K+1 else N:=K-1;
K:=(M+N) div 2
end;
if
M>N then K:=0;
end;
procedure BVyber(M,N :
integer; var A : Pole; C :
TypPrvku; var K : integer);
begin
K:=(M+N) div
2;
if
M<=N then
begin
if
C>A[K] then
BVyber(A,K+1,N,C,K)
else if
C<A[K] then
BVyber(A,M,K-1,C,K)
end
else
K:=0
end;
procedure
BVyberVsechny(M,N : integer; var
A : Pole; C : TypPrvku; var
K,L : integer);
begin
L:=0;
K:=(M+N) div
2;
while
(C<>A[K]) and (M<=N)
do
begin
if
C>A[K] then M:=K+1 else N:=K-1;
K:=(M+N) div 2
end;
if
M>N then K:=0
else
begin
L:=K;
while (A[K]=C) and
(K>M) do K:=K-1;
if A[K]<>C then
K:=K+1;
while (A[L]=C) and
(L<N) do L:=L+1;
if
A[L]<>C then L:=L-1
end
end;
Třídění
· prvky v poli s indexy (nebo souboru resp. jiné datové struktuře)
· vnitřní třídění (prvky jsou v operační paměti) - důležitý je počet porovnávání (někdy i počet výměn)
· vnější třídění (prvky jsou v souborech na disku) - důležitý je počet přístupů na disk (čtení|zápis)
Metody třídění
1. výběr minima (maxima)
2. zatřiďování
3. bublinková
4. slučování
5. shell sort
6. heap sort
7. quick sort
existují i další
Časová složitost metod třídění
metody 1.-3. mají složitost 
, další metody 
Přesná omezení počtu porovnání
n - počet prvků, p - počet porovnání
|
výběr minima |
|
|
|
zatřiďování |
|
|
|
bublinkové |
|
Lze optimalizovat - sledování, kde došlo k poslední záměně (zrychlení, pokud nejsou právě opačně), bublání zepředu i zezadu |
|
slučování |
|
|
Algoritmy třídění
vzestupné třídění úseku M..N číselného pole A
================================================================================