基数ソート in Rust

基数ソート radix sort

• O(N logN)
• バケットソートは巨大な数字が存在するとその分箱の数を用意する必要がある
• 基数ソートは各桁に対してバケットソートすることで最後にソートすることができる

// Number of Digits
const D: usize = 3_usize;
// Number of Elements of Array
const N: usize = 10_usize;

fn main() {
    let mut a: [u32;N] = [123, 1, 11, 7, 215, 0, 24, 32, 27, 333];
    radix_sort(&mut a);
    println!("a = {:?}", a);
}

fn radix_sort(a: &mut [u32;N]) {
    for i in 0..D {
        let exp: usize = 10usize.pow(i as u32);
        bucketsort(a, exp);
    }
}

fn bucketsort(a: &mut [u32;N], exp: usize) {

    // ソート後配列における値ごとの開始位置
    let mut output = [0_u32; 10];

    // 出現回数を求める
    let mut count = [0_usize; 10];

    // 出現回数を数える
    for i in 0..N {
        let index: usize = (a[i] as usize) / exp;
        count[ index % 10 ] += 1;
    }

    // 開始位置計算
    for i in 1..10 {
        count[i] += count[i-1];
    }

    for i in (0..=N-1).rev() {
        let index: usize = (a[i] as usize) / exp;
        output[count[(index) % 10] - 1] = a[i];
        count[ (index) % 10 ] -= 1;
    }

    for i in 0..N {
        a[i] = output[i];
    }
}