Rustでソートアルゴリズム (1)バブルソート・コムソート

概要

Rustの勉強の為にソートを実装してみることとする。
１回目としては、一番簡単なバブルソートを実装し、その発展形であるコムソートを実装する。

前提条件

Rustのバージョンは1.19.0とします。

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

バブルソート

Wikipediaでの説明

BubbleSort

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

実行して見ましたが、やはり遅い……
1000要素で動かした場合、標準ソートと比べて30倍ぐらいの時間がかかりました。

コムソート

バブルソートを改良したソートです。
Wikipediaでの説明

CombSort

fn sort<T: PartialOrd>(source: &mut [T]) {
    let mut h = source.len();
    let mut is_swaped = true;

    while is_swaped || h > 1 {
        if h > 1 {
            h = h * 10 / 13;
        }

        is_swaped = false;
        let mut i = 0;
        while i < source.len() - h {
            if source[i] > source[i + h] {
                source.swap(i, i + h);
                is_swaped = true;
            }
            i += 1;
        }
    }
}

そこそこ速くなります。
1000要素で動かした場合、標準ソートと比べて倍ぐらいの時間で完了しました。