|
Tato metoda připomíná způsob, jakým si karetní hráči obvykle řadí karty v ruce: z balíčku rozdaných karet berou jednu kartu po druhé a zařadí ji na správné místo podle velikosti a barvy. Je-li třeba, odsunou doprava karty, které zařadili již dříve. Při popisu třídění
pole přímým vkládáním
vyjdeme z představy dvou posloupností,
zdrojové a cílové. V i-tém kroku
vezmeme i-tý prvek zdrojové
posloupnosti a zařadíme jej na správné místo v cílové posloupnosti. Protože zdrojová i cílová
posloupnost leží na témže místě paměti, budeme postupovat takto: První prvek pole ponecháme na místě. Vezmeme druhý prvek a porovnáme jej s prvním. Je-li větší, ponecháme
jej na místě, jinak jej zařadíme na první místo a prvek z prvního místa
odsuneme na druhé místo. Vezmeme třetí prvek, zjistíme, zda patří na první, druhé nebo třetí
místo, zařadíme jej a prvky za ním podle potřeby odsuneme. atd. Příklad 1.1
Chceme utřídit
posloupnost (3,
2, 17,
1, 8,
5), viz obr. 1.1. Šipky na obrázku ukazují směry
přesunů v jednotlivých krocích; v závorkách je dosud netříděná část
pole.
Obr.
1.1
Než se pustíme do zápisu algoritmu přímého vkládání v Pascalu, musíme si ujasnit, jak vložit prvek na správné místo v utříděné části posloupnosti. Nejjednodušší možnost
je asi tato: vkládaný prvek je na i-tém
místě, vlevo od něj je již setříděná část pole. Porovnáme ho tedy s
prvkem bezprostředně vlevo od něj. Pokud je vkládaný prvek větší nebo
roven svému levému sousedu, je již na správném místě. V opačném případě
tyto dva prvky prohodíme a vkládaný prvek opět porovnáme s prvkem, který
je v poli bezprostředně vlevo od něj atd. Podívejme se na vkládání
prvku 1
v příkladu 1.1
(třetí řádek na obr. 1.1).
Tento prvek stojí na 4. místě. Porovnáme jej tedy s prvkem na třetím
místě (17); protože je
menší, prohodíme je, takže dostaneme posloupnost 2, 3,
1, 17....
Dále porovnáme prvek 1
s prvkem na druhém místě (2).
Protože 1 je menší, opět
je prohodíme, takže dostaneme posloupnost 2, 1,
3, 17...
Po dalším porovnání a prohození dostaneme posloupnost, kterou vidíme
ve 4. řádku obrázku.
Hledání správného místa
skončí, jestliže bude prvek vlevo menší než vkládaný prvek nebo jestliže
jsme již dospěli na první místo v poli. To jsou dvě podmínky; jedné z
nich se můžeme zbavit (a tak algoritmus poněkud zjednodušit), jestliže použijeme
zarážku
. Pole a bude místo a[1] začínat
prvkem a[0], tj. deklarujeme je příkazem var a: array [0..n] of
prvek; a do a[0] uložíme hodnotu vkládaného prvku. Porovnávání pak skončí v nejhorším případě těsně před zarážkou, neboť vkládaný prvek bude mít stejný klíč jako zarážka. Procedura pro třídění přímým vkládáním může vypadat takto (n je počet prvků ve tříděné posloupnosti): procedure
PříméVkládání; var
i,j: index; x: prvek;
{pomocná proměnná} begin for i := 2 to n do begin x := a[i]; a[0] := x;
{definice zarážky} j := i-1; while x.klíč < a[j].klíč do begin a[j+1] := a[j];
{odsouvání prvků doprava} dec(j) end; a[j+1] := x;
{vložení prvku na správné místo} end end; Analýza algoritmu přímého vkládání
Při rozboru této metody se budeme opírat o proceduru PříméVkládání. Je zřejmé, že nejhorší možný případ nastane, jestliže bude zdrojová posloupnost uspořádána v opačném pořadí - jako první bude největší prvek, jako poslední prvek nejmenší. Potom budeme muset v i-tém kroku, při vkládání i-tého prvku, provést Ci = i-1 porovnání a Mi = i+1 přesunů včetně uložení hodnoty vkládaného prvku do zarážky. Celkový počet porovnání
a přesunů v nejhorším případě potom bude
Nejlepší možný případ nastane, když bude zdrojová posloupnost již správně uspořádána. V takovém případě potřebujeme v každém kroku pouze jedno porovnání, Ci = 1. Počet přesunů v popsané proceduře bude v každém kroku[1] Mi = 3. Celkový počet porovnání a přesunů v nejlepším případě potom bude
Budeme-li předpokládat, že všechny permutace zdrojové posloupnosti jsou stejně pravděpodobné, můžeme tvrdit, že průměrný počet porovnání bude Ci = i/2 a počet přesunů bude Mi = Ci + 2. Odtud pro průměrné počty operací odvodíme
Průměrný počet porovnání i přesunů je tedy O(n2). Poznamenejme, že
metoda přímého vkládání je stabilní v tom smyslu, že prvky se stejnou hodnotou
klíče budou v cílové posloupnosti uloženy ve stejném pořadí jako v
posloupnosti zdrojové.
[1]Algoritmus třídění přímým vkládáním lze naprogramovat tak, že
tyto zbytečné přesuny odpadnou, výsledná procedura bude však složitější.
|
|