Rustでソートアルゴリズム (3)選択ソート・ヒープソート

概要

選択ソートを実装し、その発展形であるヒープソートを実装する。

前提条件

前回と同様にRustのバージョンは1.19.0とします。

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

選択ソート

Wikipediaでの説明
配列から一番小さな値を探して先頭に配置、残りの配列から一番小さな値を探して２番目に配置…と続けるソート。

SelectionSort

fn sort<T: PartialOrd>(source: &mut [T]) {
    for i in 0..(source.len() - 1) {
        let mut k = i;
        for j in (i + 1)..source.len() {
            if source[j] < source[k] {
                k = j;
            }
        }
        if k != i {
            source.swap(i, k);
        }
    }
}

正直遅い。使い道はイテレータの実装で使えるかもしれないぐらい。

ヒープソート

Wikipediaでの説明
選択ソートで行う、一番小さな（大きな）値を探す方法を、ヒープを使い、高速化したソート。
どんなデータでも$O(n \log n)$のオーダーとなる。

HeapSort

fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    let ls = source.len() >> 1;
    let mut i = ls;
    while i > 0 {
        i -= 1;
        let j = source[i].clone();
        let mut n = i;
        while n < ls {
            let mut l1 = (n << 1) + 1;
            if l1 + 1 < source.len() && source[l1] < source[l1 + 1] {
                l1 += 1;
            }
            if j >= source[l1] {
                break;
            }
            source[n] = source[l1].clone();
            n = l1;
        }
        source[n] = j;
    }
    let mut i = source.len();
    while i > 0 {
        i -= 1;
        let j = source[i].clone();
        source[i] = source[0].clone();

        let mut n = 0;
        let mut leaf = 1;
        while leaf < i {
            if leaf + 1 < i && source[leaf] < source[leaf + 1] {
                leaf += 1;
            }
            if j >= source[leaf] {
                break;
            }
            source[n] = source[leaf].clone();
            n = leaf;
            leaf = (n << 1) + 1;
        }
        source[n] = j;
    }
}

前半はUpheap操作にてヒープを作成、後半ではDownheap操作によりヒープを維持している。
この時点で標準ソートより速かったりする。
要素数が大きい場合(n≧4096)には標準ソートより若干遅い程度となる。

unsafeを使って高速化してみる

HeapSort(Unsafe)

fn sort<T: PartialOrd>(source: &mut [T]) {
    let ls = source.len() >> 1;
    let mut i = ls;
    let ptr = source.as_mut_ptr();
    let len = source.len();
    while i > 0 {
        i -= 1;
        let mut n = i;
        unsafe {
            let mut j: T = mem::uninitialized();
            ptr::copy_nonoverlapping(ptr.offset(i as isize), &mut j, 1);
            while n < ls {
                let mut l1 = (n << 1) + 1;
                if l1 + 1 < len &&
                    *(ptr.offset(l1 as isize)) < *(ptr.offset((l1 + 1) as isize))
                {
                    l1 += 1;
                }
                if j >= *(ptr.offset(l1 as isize)) {
                    break;
                }
                ptr::copy_nonoverlapping(ptr.offset(l1 as isize), ptr.offset(n as isize), 1);
                n = l1;
            }
            ptr::copy_nonoverlapping(&j, ptr.offset(n as isize), 1);
            mem::forget(j);
        }
    }
    let mut i = len;
    while i > 0 {
        i -= 1;
        unsafe {
            let mut j: T = mem::uninitialized();
            ptr::copy_nonoverlapping(ptr.offset(i as isize), &mut j, 1);
            ptr::copy_nonoverlapping(ptr, ptr.offset(i as isize), 1);
            let mut n = 0;
            let mut leaf = 1;
            while leaf < i {
                if leaf + 1 < i &&
                    *(ptr.offset(leaf as isize)) < *(ptr.offset((leaf + 1) as isize))
                {
                    leaf += 1;
                }
                if j >= *(ptr.offset(leaf as isize)) {
                    break;
                }
                ptr::copy_nonoverlapping(ptr.offset(leaf as isize), ptr.offset(n as isize), 1);
                n = leaf;
                leaf = (n << 1) + 1;
            }
            ptr::copy_nonoverlapping(&j, ptr.offset(n as isize), 1);
            mem::forget(j);
        }
    }
}

ここまでやっても標準ソートと比較してn≧4096の領域で１割ほど遅い。
なおn<4096の領域では全く歯が立たない。