Radix sort

Radix sort (přihrádkové řazení) je stabilní řadící algoritmus používaný především k řazení řetězců totožné délky.

Princip

Princip radix sortu vychází přímo z definice stabilního řazení – řadicí algoritmus je stabilní, pokud zachovává pořadí klíčů, které mají stejnou hodnotu (tj. pokud stuktury seřadíme napřed dle klíče A, poté podle klíče B, tak jsou seřazeny podle B, a kde jsou si hodnoty B rovny, tam jsou struktury v pořadí daném klíčem A).

Radix sort řadí řetězce totožné délky tak, že nad každým znakem od konce těchto řetězců zavolá stabilní řadicí algoritmus (seřadí řetězce podle posledního znaku, poté podle předposledního...). Po n-tém průchodu jsou řetězce seřazeny dle všech pozic znaků.

Asymptotická složitost

Asymptotická složitost radix sortu je $O(m \\cdot C(n))$ , kde je počet znaků řazených řetězců, je velikost dat a C(n) je složitost vnitřního stabilního řadícího algoritmu (za tímto účelem je často použit counting sort).

function radixSort(String s)
    for i in (s.length - 1)  -> 0 do
        stableSort(s[i])

/**
 * Radix sort - prihradkove razeni 
 * Od nejnizsi hodnoty - vnitrni stabilni razeni: counting sort
 * @param array pole k serazeni
 * @param dimension rozmer dat (fixni)
 * @return serazene pole
 */
public static String[] radixSort(String[] array, int dimension){
    for(int i = dimension - 1; i >= 0 ; i--){
        array = countingSortForRadix(array, i); //stabilne serad dle i-te pozice
    }
    return array;
}
/**
 * Counting sort pro radix sort - radi pole dle hodnoty na pozici
 * @param array pole k serazeni
 * @param position pozice, podle ktere se bude radit
 * @return serazene pole dne pozice
 */
public static String[] countingSortForRadix(String[] array, int position){
    String[] aux = new String[array.length];
 
    char min = array[0].charAt(position);
    char max = array[0].charAt(position);
    for(int i = 1; i < array.length; i++){
        if(array[i].charAt(position) < min) min = array[i].charAt(position);
        else if(array[i].charAt(position) > max) max = array[i].charAt(position);
    }
 
    int[] counts = new int[max - min + 1];
 
    for(int i = 0;  i < array.length; i++){
        counts[array[i].charAt(position) - min]++;
    }
 
    counts[0]--;
    for(int i = 1; i < counts.length; i++){
        counts[i] = counts[i] + counts[i-1];
    }
 
    for(int i = array.length - 1; i >=0; i--){
        aux[counts[array[i].charAt(position) - min]--] = array[i];
    }
 
    return aux;
}

Princip

Asymptotická složitost

Kód

Doporučujeme