Triedenie priamym vkladaním

Triedenie priamym vkladaním (anglicky: Insert Sort) je jednoduchý triediaci algoritmus usporadúvajúci prvky poľa zloženého z celých, reálnych čísel a reťazcov. Patrí medzi porovnávacie (komparačné) a asociatívne algoritmy.

Vlastnosti

Insert Sort nepatrí medzi výhodné algoritmy triedenia, nakoľko pracuje s operačnou zložitosťou O(n²). Oproti vylepšeným triediacim algoritmom ako napr. Quicksort, triedenie haldou alebo Dobosiewiczovo triedenie je málo efektívny. Ale výsledkom jeho triedenia je stabilné pole (čiže zachová relatívne usporiadanie duplicitných kľúčov triedených prvkov). Insert Sort sa vyznačuje taktiež jednoduchou realizáciou a vhodný je hlavne na takmer usporiadané pole s malým počtom prvkov(pod 2 000). Pri usporadúvaní už usporiadaného poľa je Insert Sort dokonca rýchlejší ako Quicksort, pretože každý nový prvok porovnáva len s posledným v danom poli.

Algoritmus triedenia

Algoritmus Insert Sortu vyberá postupne po jednom prvku z poľa a porovnáva ho s ostatnými prvkami, pričom sa tento krok opakuje počet prvkov - 1 krát. Keď narazí na menšiu hodnotu, nájdený prvok sa presunie za vybraný prvok. Týmto sa pole rozdelí na usporiadanú (ľavá) a neusporiadanú (pravá) časť. Vždy sa vkladajú prvky len jednosmerne a to z neusporiadanej časti do usporiadanej. Takto sa vzostupne usporiada celé pole prvkov. Vhodnou modifikáciou podmienok algoritmu možno dosiahnuť i zostupné usporiadanie.

Hodnoty

Pri vhodnom vstupnom poli je minimálny počet porovnaní n-1 a presunov 2(n - 1). Najhorší prípad nastane pri totálne neusporiadanom poli s veľkým množstvom prvkov, kedy počet porovnaní narastie až na (n² + n - 2)/2 a počet presunov na (n² + 3n - 4)/2. Priamo úmerne narastá tiež náročnosť na veľkosť operačnej pamäte počítača.

Externé odkazy

• Algoritmy usporadúvania
• Insert Sort v praxi Archivované 2008-08-09 na Wayback Machine