Insertion sort

Pokročilé řadicí algoritmy

SSŠVT

Insertion sort

Princip

Insertion sort bere prvky jeden za druhým ze vstupní (nesetříděné) kolekce a zatřiďuje je (vkládá, proto insertion) na správnou pozici ve výstupní (setříděné) kolekci.

Algoritmus

Dá se dělat i tzv. in-place, tj. v původní nesetříděné kolekci, ale názornější je, představíme-li si vstup jako jednu nesetříděnou dynamickou kolekci a výstup jako druhou dynamickou kolekci se stejnými prvky, ale tentokrát již setříděnou.

Předpokládejme, že třídíme od nejmenšího prvku po největší. Na začátku je nesetříděná kolekce "plná", zatímco ta setříděná je zatím prázdná. Jelikož jde o dynamické kolekce, podržíme se terminologie .NET-u a budeme kolekcím říkat seznamy.

Následující postup opakujeme v cyklu, dokud je v nesetříděném seznamu aspoň jeden prvek:

1. Vezmeme (odebereme) prvek z nulté pozice v nesetříděném seznamu. Tomuto prvku říkáme v této iteraci aktuální prvek.
2. Pokud je setříděný seznam prázdný, aktuální prvek do něj přidáme (metoda Add).
3. Pokud jsou v setříděném seznamu již nějaké prvky, procházíme setříděný seznam postupně od začátku a hledáme "vhodné" místo, kam bychom aktuální prvek zatřídili.
4. Vhodnému místu budeme v této iteraci říkat správná pozice.
5. Mohou nastat 3 případy:
   
   
   1. Aktuální prvek je menší než prvek na nulté pozici v setříděném seznamu.
      Správná pozice v setříděném seznamu je tedy pozice s indexem nula. Jinými slovy - aktuální prvek musíme zatřídit (vložit) na začátek seznamu před jeho první prvek.
   2. Aktuální prvek je větší (nejhůře roven) než nějaký prvek A v setříděném seznamu a zároveň je menší než prvek B, který bezprostředně následuje za prvkem A.
      Správná pozice v tomto případě je pozice s indexem prvku A. Jinými slovy - aktuální prvek musíme zatřídit (vložit) někam dovnitř seznamu mezi prvky A a B.
   3. Aktuální prvek je větší (nejhůře roven) než prvek na poslední pozici v setříděném seznamu.
      Správná pozice v setříděném seznamu je pozice s indexem o jednu větším než je index posledního prvku seznamu. Jinými slovy - aktuální prvek musíme zatřídit (přidat) za konec seznamu, za jeho poslední prvek.
   První dva případy vyřešíme tak, že aktuální prvek zatřídíme pomocí metody Insert, tj. aktuální prvek vložíme na správnou pozici a prvky, které už v seznamu jsou, počínaje prvkem na správné pozici, tím pádem "odsuneme" o jednu pozici dál (jejich indexy se zvětší o jedničku). Poslední případ vyřešíme přidáním aktuálního prvku (metoda Add) na konec seznamu.
6. Opakujeme postup od začátku až do vyprázdnění nesetříděného seznamu.

Ilustrace

Příklad

Chceme např. setřídit takovouto kolekci čísel: 10, -5, 2, 0, 12, 1

Odkaz

Více informací: https://en.wikipedia.org/wiki/Insertion_sort