Urejanje po delih (radix sort)


Glavna stran

Implementacija LSD radix sort

Spodnji diagram prikazuje LSD radix urejanje od desne proti levi bit za bitom. I-ti stolpec dobimo iz (i-1)-tega stolpca z izvlečenjem vseh ključev z 0 na i-tem mestu in vračanjem nad ključe z 1 na i-tem mestu. Če je (i-1)-ti stolpec "poravnan" na (i-1) sledečih bitih ključev pred operacijo, potem je po operaciji i-ti stolpec "poravnan" s sledečimi i biti ključev. To je zagotovljeno, če za urejanje uporabljamo metodo, ki je stabilna (npr. key-indexed counting).

Za 5-mestne ključe za urejanje potrebujemo 5 korakov/faz premikanja od desne proti levi skozi ključe. Pri urejanju zapisov z eno-mestnimi ključi velja, da se zapisi, s ključi 0 pojavijo pred zapisi s ključi 1. Premik ključev v tretji fazi je označen eksplicitno.

LSD radix urejanje