Counting sort

O(n + k)

Counting sort je neporovnávací řazení pro celá čísla z malého rozsahu. Jedním průchodem spočítá, kolikrát se každá hodnota vyskytuje, a pak projde počty od nejmenší hodnoty po největší a každou zapíše tolikrát, kolik jí napočítal. Žádná porovnání ani prohození, takže běží v O(n + k), kde k je velikost rozsahu hodnot — překonává hranici O(n log n) porovnávacích řazení, když k není o moc větší než n. Cenou je paměť a omezení rozsahu: hodí se na věci jako věk, skóre nebo bajty a je to stabilní stavební kámen uvnitř radix sortu.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Najdi rozsah hodnot a vytvoř přihrádku pro každou hodnotu.
  2. Projdi pole a počítej, kolikrát se každá hodnota vyskytuje.
  3. Projdi počty odspodu nahoru a vypiš každou hodnotu tolikrát.
  4. Znovu sestavené pole je seřazené — nikdy nedošlo k žádnému porovnání.

Pseudokód

1countingSort(a):                    # O(n + k)2  k ← max(a) − min(a) + 13  count ← array of k zeros4  for v in a: count[v − min]++       # tally each value5  out ← []6  for v from 0 to k-1:7    append (v + min) count[v] times   # emit in order8  return out