Insertion sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Insertion sort v akci na několika náhodných číslech

Řazení vkládáním (anglicky insertion sort) je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus Insertion Sort pracuje tak, že prochází prvky postupně a každý další nesetříděný prvek zařadí na správné místo do již setříděné posloupnosti.

Je to jeden z nejrychlejších algoritmů s kvadratickou časovou složitostí. Je asymptoticky pomalejší než pokročilé algoritmy jako třeba quicksort nebo mergesort, ale má jiné výhody.

Výhody[editovat | editovat zdroj]

  • jednoduchá implementace
  • efektivní na malých množinách
  • efektivní na částečně seřazených množinách (běží v čase O(N + d), kde d je počet transpozic prvků množiny)
  • efektivnější než většina ostatních O(N^2) algoritmů (selection sort, bubble sort), průměrný čas je \frac{N^2}{4} a v nejlepším případě je dokonce lineární
  • řadí stabilně (nemění vzájemné pořadí prvků se stejnými klíči)
  • vyžaduje pouze O(1) paměti (kromě vlastního vstupu)
  • je online algoritmem, tzn. dokáže řadit data tak, jak přicházejí na vstup

Princip[editovat | editovat zdroj]

  1. Posloupnost rozdělíme na seřazenou a neseřazenou tak, že seřazená obsahuje první prvek posloupnosti
  2. Z neseřazené části vybereme první prvek a zařadíme jej na správné místo v seřazené posloupnosti
  3. Prvky v seřazené posloupnosti posuneme o jednu pozici doprava
  4. Seřazenou část zvětšíme o jeden prvek. Naopak neseřazenou část o jeden prvek zleva zmenšíme
  5. Kroky 2-5 aplikujeme až do úplného seřazení neseřazené části

Algoritmus[editovat | editovat zdroj]

insertionSort(A)
   pro i od 1 do počtu prvků opakuj:
       hodnota = A[i];
       j = i-1;
       pokud j >= 0 a zároveň A[j] > hodnota opakuj:
           A[j+1] = A[j];
           j = j--;
       A[j+1] = hodnota;