ハイサイ！んながんじゅーやいびーみ？

概要

Rustでクイックソートという並べ替えアルゴリズムを実装してみます。

並べ替えアルゴリズムとは

プログラミングの各言語に並べ替え機能が標準機能として実装されています。大体は配列のメソッドとして.sort()のようなものです。

筆者は本記事を書くまで、並べ替えの内部を意識したことがありませんでしたが、無論、魔法の杖を振って綺麗に並ぶわけではなく、裏で凝りに凝ったロジックが走っているのでした。

配列を並べ替えるためには、並べ替えのアルゴリズムを考えて言語の標準機能として実装する必要があります。現代プログラミングの勃発以前からも、並べ替えアルゴリズムについて考察し発案する偉大な方々がいらっしゃいましたが、1950年代に発明されたアルゴリズムが今も現役で使われている場合があります。

並べ替えアルゴリズムはそれぞれにパフォーマンスの違いがあり、最適な使用例があります。また、煩雑さ、実装の難易度も違います。

全てのアルゴリズムとパフォーマンスの特徴はWikipediaで綺麗にまとまっていますので一瞬見て見てください。

クイックソートとは

1960年に発明されたアルゴリズムで、実装難易度が中級レベルです。パフォーマンスは、すでに並べてある配列という最悪のケースでなければ、そこそこ早いです。

アルゴリズムの概念は、"divide and conquer"（分離して制覇する）という考え方で配列を分割して回帰的に並べ替えるものです。任意なインデックスを選んで、それをピボット値として、ピボット値より高いものはピボット値のインデックスの後に回し、ピボット値より低いものはピボット値のインデックスより前におきます。

上記の流れで以下の順を踏まえて並べ替えを進めます：

ピボット値を選定する（任意で最後の値にするのが簡単ですが、ピボット値選定にも色々と深い論理があります）
上記の説明通りに、配列をピボット値のインデックスで分割して全ての値を比べて分ける。
回帰：上記の左と右に分割された子配列に同じ処理を繰り返す。
回帰処理でこれ以上並べ替えられないところまで行けば自然に終了します。

上記の説明通りに実装していきましょう！

回帰なし分割ロジックから入る

回帰処理は筆者には難しいのでまず最初に配列の分割の関数を書きましょう。

fn partition<T>(slice: &mut [T]) -> Option<usize>
where
    T: Ord,
{
    if slice.len() < 2 {
        return None;
    }
    /* 二つしかないのであればそれだけチェックして終わり */
    if slice.len() == 2 {
        if slice[0] > slice[1] {
            slice.swap(0, 1);
        }
        return None;
    }

    /* ピボット選定（最後の値） */
    let mut p_i = slice.len() - 1;

    /* 左から進んで並べ替えていく */
    let mut i = 0;
    while i < p_i {
        if slice[i] > slice[p_i] {
            // ピボット値より大きいから、ピボット値の右側にまわないと
            slice[i..=p_i].rotate_left(1);
            p_i -= 1; // ピボット値のインデックスがその分左にずれる！
        } else {
            // ピボット値より左のままでいいので進む
            i += 1
        }
    }

    Some(p_i)
}

引数に配列の参照子をもらいますが、ジェネリック型TにはOrdトレートが実装されている条件が付きます。Ordは完全な比較ができることを意味します、つまり1 > 0はいつもtrueを返すことを意味しています。

色々と起きていますが、まず最初に、処理をしなくていい例外を省いて、これ以上並べ替えることができないことを意味するNoneを返します。

それから、ピボット値を選定して分割していきます。

分解で左から読んで、ピボット値のインデックスに当たるまで進みますが、ピボット値より大きい値を見つけた時のみ、ちょっと工夫してstd::slice::rotate_leftを使います。

このrotate_leftはすごく面白くて、上記のように配列のsliceに対してメモリアロケーションをせずに自由に一交換ができます。std::slice::swapと近いのですが、考えようによってはもっと柔軟に使えます。

let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
a[1..5].rotate_left(1);
assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);

今回の場合、筆者はrotate_leftがイメージ的にわかりやすかったから使いました。

最後に重要な部分ですが、分割処理が終わった後、ピボット値のインデックスをSome(p_i)として返しています。これはまだ分割・並べ替えが必要かもしれないことを意味しています。回帰処理の自然消滅の鍵になります。

テストもついでに書いておきましょう。

mod tests {
    use super::*;

    #[test]
    fn can_partition() {
        let mut v = vec![4, -1, 5, -2, 1];

        let pivot_i = partition(&mut v).unwrap();

        assert_eq!(&v[pivot_i], &1);
        assert!(&v[..pivot_i].iter().all(|n| n <= &v[pivot_i]));
        assert!(&v[pivot_i..].iter().all(|n| n >= &v[pivot_i]));
    }

    #[test]
    fn can_finish() {
        let mut v = vec![4, 5];

        let pivot_i = partition(&mut v);

        assert!(pivot_i.is_none());
    }
}

これで回帰処理じゃない部分をクリアできました！

回帰処理の関数を分けて作る

回帰処理を回帰処理だけで分けて考えたいので、関数を分けましょう。

さっきのpartitionの関数の戻り値をOption<usize>にしていた訳に触れましたが、なんらかの方法でこれ以上回帰処理しなくていいことを知らせる術が必要なので、そのようにしました。

また、回帰するときに、分割した配列の左手の子配列と右手の子配列が生まれるので、毎回左と右で回帰していきます。

fn recurse<T>(slice: &mut [T], init: usize)
where
    T: Ord,
{
    let lhs = partition(&mut slice[..init]);

    if let Some(i) = lhs {
        recurse(&mut slice[..init], i);
    }

    let rhs = partition(&mut slice[init..]);

    if let Some(i) = rhs {
        recurse(&mut slice[init..], i);
    }
}

綺麗に正解を出していますが、筆者はずっとloopなんとかで踏ん張ってアホなことをしていて、loopなんぞ要らんと気づいたら非常にスッキリしたロジックが生まれてあきれました。

注意していただきたいのは、回帰していく時に、左手と右手に配列を分けていきますが、引数としてもらうinitつまりピボット値のインデックスはどれにも含めません。一回ピボット値のインデックスが決まれば2度と変わらないという面白い現象です。

`sort`関数を定義して組み合わせる

回帰処理の部分と、実際に配列を分割するロジックを書きましたが、引火する関数が必要です。それが以下の通りです。

fn sort<T>(slice: &mut [T])
where
    T: Ord,
{
    let p_i = partition(slice);

    if let Some(init) = p_i {
        recurse(slice, init);
    }
}

これだけで並べ替えが効くのです！分けて実装すると簡単に感じます。実装してから記事を書くと、簡単そうに見えます！

テストも追加します。

    #[test]
    fn quicksort_works() {
        let mut v = vec![0, -4, 6, 9, -1, 0, 1, 4, 7, 1, -3];

        sort(&mut v);

        assert_eq!(v, vec![-4, -3, -1, 0, 0, 1, 1, 4, 6, 7, 9]);
    }

パチパチパチ

まとめ

Rustでクイックソートのもっとも簡単なバージョンを実装しましたが、いかがでしょうか？

筆者は、腕を試そうと思ってWikipediaの説明だけ読んで、実装してみましたが非常に愉快でした。Rustは楽しいです。

まさか、並べ替えがこれほど複雑だとも思いませんでした

Rustでクイックソートの並べ替えアルゴリズムを実装しましょう

概要

並べ替えアルゴリズムとは

クイックソートとは

回帰なし分割ロジックから入る

回帰処理の関数を分けて作る

sort関数を定義して組み合わせる

まとめ

`sort`関数を定義して組み合わせる