Rustでソートアルゴリズム (6)バケットソート・基数ソート

概要

適用条件は厳しいが、$O(n)$の速度となるソートを実装する。

前提条件

これまでと同様にRustのバージョンは1.19.0とします。

% rustc --version
rustc 1.19.0 (0ade33941 2017-07-17)

バケットソート

Wikipediaでの説明

まず[u8]と[i8]に対するソートを下に示す

BucketSort

fn sort(source: &mut [u8]) {
    let tmp = source.to_vec();
    let mut bucket = [0; 257];

    for i in 0..source.len() {
        bucket[source[i] as usize + 1] += 1;
    }
    for i in 2..bucket.len() {
        bucket[i] += bucket[i - 1];
    }
    for i in 0..tmp.len() {
        let val = tmp[i];
        source[bucket[val as usize]] = val;
        bucket[val as usize] += 1;
    }
}

fn sort(source: &mut [i8]) {
    let tmp = source.to_vec();
    let mut bucket = [0; 257];

    for i in 0..source.len() {
        bucket[(source[i] as isize + 1 - i8::min_value() as isize ) as usize] += 1;
    }
    for i in 2..bucket.len() {
        bucket[i] += bucket[i - 1];
    }
    for i in 0..tmp.len() {
        let val = tmp[i];
        let pos = (val as isize - i8::min_value() as isize) as usize;
        source[bucket[pos]] = val;
        bucket[pos] += 1;
    }
}

この種のソートは、比較を行っているわけではないため、それぞれの型に対して実装する必要がある。したがって、汎用的なライブラリには不向きとなってくる。
なお、このソートは、16ビット整数だと、次のコードとなる。

BucketSort(16bit)

fn sort(source: &mut [u16]) {
    let tmp = source.to_vec();
    let mut bucket = [0; 65537];

    for i in 0..source.len() {
        bucket[source[i] as usize + 1] += 1;
    }
    for i in 2..bucket.len() {
        bucket[i] += bucket[i - 1];
    }
    for i in 0..tmp.len() {
        let val = tmp[i];
        source[bucket[val as usize]] = val;
        bucket[val as usize] += 1;
    }
}

fn sort(source: &mut [i16]) {
    let tmp = source.to_vec();
    let mut bucket = [0; 65537];

    for i in 0..source.len() {
        bucket[(source[i] as isize + 1 - i16::min_value() as isize ) as usize] += 1;
    }
    for i in 2..bucket.len() {
        bucket[i] += bucket[i - 1];
    }
    for i in 0..tmp.len() {
        let val = tmp[i];
        let pos = (val as isize - i16::min_value() as isize) as usize;
        source[bucket[pos]] = val;
        bucket[pos] += 1;
    }
}

バケツサイズが65537個になっている。
このまま32ビットに拡張することは現実的に不可能である。
ただ、最大・最小値が一定の範囲内であれば、32ビット整数だろうが適用可能である。

基数ソート

Wikipediaでの説明
バケットソートの弱点である、32ビット整数等にも適用可能な様に拡張したソートである。やり方次第では浮動小数点数にも適用可能である。

RadixSort(32bit)

fn sort(source: &mut [i32]) {
    fn sort_radix(source: &[i32], dest: &mut [i32], digit: usize, sign: bool) {
        let bit_digit = digit << 3;
        let mut bucket = [0; 257];
        let sign_mask = if sign { 0x80 } else { 0 };
        for i in 0..source.len() {
            bucket[(((source[i] >> bit_digit) & 0xFF) as usize ^ sign_mask) + 1] += 1;
        }
        for i in 2..bucket.len() {
            bucket[i] += bucket[i - 1];
        }
        for i in 0..source.len() {
            let val = source[i];
            let pos = ((val >> bit_digit) & 0xFF) as usize ^ sign_mask;
            dest[bucket[pos]] = val;
            bucket[pos] += 1;
        }
    }

    let mut tmp = source.to_vec(); // メモリ確保
    sort_radix(source, &mut tmp, 0, false);
    sort_radix(&tmp, source, 1, false);
    sort_radix(source, &mut tmp, 2, false);
    sort_radix(&tmp, source, 3, true);
}

fn sort(source: &mut [u32]) {
    fn sort_radix(source: &[u32], dest: &mut [u32], digit: usize, sign: bool) {
        let bit_digit = digit << 3;
        let mut bucket = [0; 257];
        let sign_mask = if sign { 0x80 } else { 0 };
        for i in 0..source.len() {
            bucket[(((source[i] >> bit_digit) & 0xFF) as usize ^ sign_mask) + 1] += 1;
        }
        for i in 2..bucket.len() {
            bucket[i] += bucket[i - 1];
        }
        for i in 0..source.len() {
            let val = source[i];
            let pos = ((val >> bit_digit) & 0xFF) as usize ^ sign_mask;
            dest[bucket[pos]] = val;
            bucket[pos] += 1;
        }
    }

    let mut tmp = source.to_vec(); // メモリ確保
    for i in 0..2 {
        sort_radix(source, &mut tmp, i << 1, false);
        sort_radix(&tmp, source, (i << 1) + 1, false);
    }
}

ベンチマークを取る限り、ある程度大きな配列に対する速度は圧倒的である。