バケットソート in Rust

Rust

バケットソート bucket sort

  • O(N logN)
  • 比較をしないソート
  • 含まれている値の種類の数が決定している必要がある ( = バケツの数)
const RANGE: usize = 10;

fn main() {
    let a = [5,4,6,7,1,3,8,2,9,0];
    let mut d = [0;RANGE];
    bucketsort(a, &mut d);
    println!("{:?}", d);
}

fn bucketsort(src:[usize;RANGE], dst: &mut [usize;RANGE]) {
    // 出現回数を求める
    let mut count:[usize; RANGE] = [0; RANGE];

    // ソート後配列における値ごとの開始位置
    let mut offset:[usize; RANGE] = [0; RANGE];

    // 出現回数を数える
    for i in 0..src.len() {
        count[ src[i] ] += 1;
    }

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

    // ソート処理
    for i in 0..src.len() {
        let target = src[i];
        // 開始位置にターゲットを入れる
        dst[offset[target]] = target;
        // ターゲットの開始位置をずらす
        offset[target] += 1;
    }
}