Insertion sort

O(n²)

Insertion sort nechává vlevo růst seřazenou část, prvek po prvku. Vezme další hodnotu, posune ji doleva přes všechny větší sousedy a vloží ji do vzniklé mezery. Je jednoduchý, stabilní a velmi rychlý na téměř seřazených datech — nejlepší případ O(n) — proto ho knihovny používají pro malé nebo skoro seřazené vstupy.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vezmi další prvek napravo od seřazené části jako „klíč“.
  2. Porovnávej ho s prvky vlevo a každý větší posuň o krok doprava.
  3. Vlož klíč do vzniklé mezery — seřazená část je o jedna delší.
  4. Opakuj, dokud nejsou vloženy všechny prvky.

Pseudokód

1insertionSort(a):                   # O(n²)2  for i from 1 to n-1:3    key ← a[i]4    j ← i - 15    while j ≥ 0 and a[j] > key:      # shift bigger ones right6      a[j+1] ← a[j]7      j ← j - 18    a[j+1] ← key                     # drop key into the gap