Radix sort

O(d·(n + b))

Radix sort uspořádá čísla zpracováním jejich číslic, nejprve od nejnižší. Každý průchod rozdělí čísla do deseti přihrádek podle aktuální číslice a pak je posbírá zpět v pořadí přihrádek; protože je rozdělení stabilní, dřív seřazené číslice zůstanou v každé přihrádce uspořádané. Po zpracování nejvyšší číslice je celé pole seřazené. S d číslicemi a základem b běží v O(d·(n + b)) — prakticky lineárně, když mají čísla omezený počet číslic. Každý průchod číslicí je sám o sobě counting sort.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni číslicí jednotek (nejnižší).
  2. Rozděl každé číslo do 10 přihrádek podle té číslice a zachovej jejich pořadí.
  3. Posbírej přihrádky zpět dohromady v pořadí.
  4. Opakuj pro každou vyšší číslici — po nejvyšší číslici je pole seřazené.

Pseudokód

1radixSort(a):                       # O(d·(n + b))2  for each digit position, LSD first:3    buckets ← 10 empty lists4    for v in a:5      d ← digit of v at this position6      buckets[d].append(v)            # stable distribute7    a ← concat(buckets[0..9])         # gather8  return a                            # sorted after the top digit