Shell sort

O(n^1.5)

Shell sort zobecňuje insertion sort: místo porovnávání jen sousedů porovnává prvky vzdálené o pevnou „mezeru“ a na nich provádí insertion sort, pak mezeru zmenší na polovinu a opakuje, dokud není mezera 1. Přesouvání prvků na velké vzdálenosti hned zkraje umožní, aby poslední průchod doběhl rychle. Doba běhu závisí na posloupnosti mezer — pro půlení zhruba O(n^1.5).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni s velkou mezerou (zde poloviční délka pole).
  2. Proveď insertion sort, který porovnává prvky takhle daleko od sebe.
  3. Mezeru zmenši na polovinu a opakuj — pole se postupně blíží seřazení.
  4. Skonči s mezerou 1, tedy běžným insertion sortem nad skoro seřazeným polem.

Pseudokód

1shellSort(a):                       # O(n^1.5)2  for gap = n/2; gap > 0; gap /= 2:3    for i from gap to n-1:           # gapped insertion sort4      temp ← a[i]; j ← i5      while j ≥ gap and a[j-gap] > temp:6        a[j] ← a[j-gap]; j ← j - gap7      a[j] ← temp