rustでアルゴリズム実装２（クイックソート）

はじめに

前回同様、アルゴリズムクイック・リファレンスをrustで実装していきたいと思います。
今回は、クイックソートの実装です。

環境

• MacBook Pro (Sierra 10.12.6 Retina)
• 2.3GHz IntelCore i7
• Memory 16GB
• NVIDIA GeForce GT 750M 2048MB Intel Iris Pro 1536MB
• rustc v.1.19.0

インストール

brew install rust

実装

wikipediaより。

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO {\displaystyle (n\log n)} (n\log n)である。
他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、
最悪の計算量はO {\displaystyle (n^{2})} (n^{2})である。また数々の変種がある。 安定ソートではない。

クイックソートを実装します。

quick.rs

// クイックソート.
pub fn sort<T: Ord+Clone+Debug>(a: &mut Vec<T>) {
    quick(0, a.len() - 1, a);
}

// クイックソート本体.
fn quick<T: Ord+Clone+Debug>(left: usize, right: usize, data: &mut Vec<T>) {
    // 左右の位置がおかしい場合、リターン.
    if left >= right { return; }

    // クイックソート.
    let mut l = left;
    let mut r = right;
    let pivot = data[(left + right) >> 1].clone();
    loop {
        // 左から小さい値、右から大きい値を検索し、交換.
        while data[l] < pivot { l += 1; }
        while pivot < data[r] { r -= 1; }

        // 追い越したらbreak.
        if l >= r { break; }

        // データ交換.
        data.swap(r, l);
        r -= 1; l += 1;
    }
    // 左/右側の配列をクイックソート.
    if left + 1 < l { quick(left, l - 1, data); } // left + 1で判定(usize型(l)のアンダフロー).
    if r + 1 < right { quick(r + 1, right, data); }
}

要素数が少なくなった場合

wikipediaには、
対象となるデータの数が少なくなったら、挿入ソートなどの別のアルゴリズムを適用することで高速化する手法が研究されている
と記載があります。

なので、要素数が少なくなった場合、挿入ソートに切り替えてみます。

以下、実装です。

quick.rs

// クイックソート.
pub fn sort<T: Ord+Clone+Debug>(a: &mut Vec<T>) {
    quick(0, a.len() - 1, a);
}

// 挿入ソート.
// 要素数が少なくなった場合、クイック→挿入へ切り替える.
fn insert_sort<T: Ord+Clone>(left: usize, right: usize, data: &mut Vec<T>) {
    for i in (left + 1)..(right + 1) {
        let mut j = i;
        while left < j && data[j - 1] > data[j] {
            let _t = data[j].clone();
            data[j] = data[j - 1].clone();
            data[j - 1] = _t;
            j -= 1;
        }
    }
}

// クイックソート本体.
fn quick<T: Ord+Clone+Debug>(left: usize, right: usize, data: &mut Vec<T>) {
    // 左右の位置がおかしい場合、リターン.
    if left >= right { return; }

    // 要素数が少ない場合、挿入ソートに切り替える（最適化）.
    if right - left < 10 {
        insert_sort(left, right, data);
    }
    else {
        // クイックソート.
        let mut l = left;
        let mut r = right;
        let pivot = data[(left + right) >> 1].clone();
        loop {
            // 左から小さい値、右から大きい値を検索し、交換.
            while data[l] < pivot { l += 1; }
            while pivot < data[r] { r -= 1; }

            // 追い越したらbreak.
            if l >= r { break; }

            // データ交換.
            data.swap(r, l);
            r -= 1; l += 1;
        }
        // 左/右側の配列をクイックソート.
        if left + 1 < l { quick(left, l - 1, data); } // left + 1で判定(usize型(l)のアンダフロー).
        if r + 1 < right { quick(r + 1, right, data); }
    }
}

要素数の判定による処理速度の推移

要素数に応じて挿入ソートに切り替えるわけですが、どのタイミングで切り替えればよいか実験してみました。
以下、実験結果です。
（いずれも、要素数十万で100回実行した結果の平均です）

ソート種別	処理時間
クイックソートのみ	0.000591sec
要素数10で挿入ソート	0.000528sec
要素数20で挿入ソート	0.000536sec
要素数30で挿入ソート	0.000541sec
要素数50で挿入ソート	0.000577sec

結果より確かに要素数が少ない場合挿入ソートに切り替えると（要素数＝10）、約10%改善されています。

結果

前回の結果と今回の結果です。
※ クイックソートは、要素数＝10で挿入ソートに切り替えています。

ソート種別	処理時間
Vec::sort	0.000456419sec
挿入	0.049269012sec
選択	0.161756264sec
ヒープ	0.057409270sec
クイック	0.000540712sec

まとめ

クイックソートはやはり早く、Vec::sortに近づきつつある速さです。
生ポインタを使用し最適化を図れば、Vec::sortより早くなるのかな？
（このあたりも勉強していきたいです）

引き続き、アルゴリズムクイックリファレンスを実装することにより、rustレベルを上げていこうと思います。
ソースはこちら