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 ta­kové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 nej­lepší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é.

Zpět

Poslední aktualizace: 29-05-2003.