スワップ編。クイックソートが出来るようになるためになるための３ステップ

2023-03-102023-03-12

ここではアルゴリズムのクイックソートを使えるようになるために、段階を経ながら学習していきたいと思います。

このトピックの目標：クイックソートができるようになるために

アルゴリズムで初歩的な内容として取り上げられることの多いソート。その中でも簡単とされるのはバブルソート。さらに賢くしたのがクイックソート。難しさとしてはクイックソートの方が複雑になるのですが、これをしっかりと理解しながら出来るようになるのが大まかな目標です。

初心者でも安心！基本的な操作から覚えて行きます

最終的にクイックソートが出来るようになるのが目標ですが、そこに到達するまでに３つのステップを設けます。

STEP

変数の入れ替え、スワップ

ソートを行う前に、変数の扱い方の基本として、スワップ処理を覚えます。変数入れ替えのついでにプログラムに出来ることも改めて確認しておきたいと思います。

STEP

バブルソートを覚える

変数スワップの他に、メソッドの再帰呼び出しなどを覚える必要があります。バブルソートの考え方は、ある意味プログラムに出来ることを理解すれば、最初に思いつきそうなソート方法です。そのため、いきなりクイックソートを覚えるより、段階としてバブルソートを覚えていきたいと思います。

STEP

クイックソートを覚える

満を持してクイックソート。これは実際に何かを並べ替えようとすると、すぐに思いつきそうな方法ではあります。あとはそれをプログラムでどう実践するかですね。

アルゴリズムを理解するために

各アルゴリズムや、プログラムの挙動を理解する前には、できるだけ現実世界に置き換えた内容で想像し易いサンプルを用意する予定です。

ぶっちゃけ並べ替えなどは、現実世界で紙に描いた番号を並べ替えをお願いするとできない人はほぼいないと思います。

はじめに覚えるべき変数の入れ替え・スワップ

最初のステップとして、変数の入れ替えを行うスワップを覚えます。

変数の入れ替えってなんぞ？

プログラムでは、変数という入れ物に数字や文字を入れて扱うことができます。また、ソート処理を行う際、この変数の中身を受け渡しを行いながら実現します。

例えば2つのコップにそれぞれ異なる液体が入っているとします(コーラとオレンジジュースとか)。ここではコップの大きさなどは考慮しません。

「この２つのコップの中身を入れ替えてください」とお願いした場合、皆さんはどうしますか？おそらく別のコップを用意して、一旦移し替えて、空になったコップに注いてもとに戻す案が思いつくのでは無いでしょうか？

変数の入れ替えは、やっている内容としてはこれと同じです！

スライム

変数は入れ物！と良く例えられますが、上記の例だとコップがまさにその状況ですね。

プログラムで変数の入れ替えを行う

今回はUnityで実行するのを想定してます。変数はスタンダードなint型でやりました。ログを表示する行が２つありますが、同じ内容で上下で結果が異なるはずです。

using UnityEngine;

public class SwapTest : MonoBehaviour
{
    void Start()
    {
        int cupA = 10;  // コーラ
        int cupB = 20;  // オレンジジュース
        Debug.Log($"cupA={cupA} cupB={cupB}");

        // スワップ処理
        int emptyCup = cupA;    // コーラを空のコップに入れる
        cupA = cupB;            // オレンジジュースをコーラのコップに入れる
        cupB = emptyCup;        // 空のコップに入れておいたコーラを
                                // オレンジジュースの入ってたコップに入れる
        Debug.Log($"cupA={cupA} cupB={cupB}");
    }
}

参照渡し!?メソッド経由でのスワップの注意点

ソート系の処理では、スワップはめちゃくちゃ多用されます。そのためメソッドにスワップ処理を集約しておきたいです。が、それには少し注意点があります。

とりあえずスワップ処理をメソッドでやってみる

上記サンプルプログラムをとりあえずメソッドに集約してみましょう。多分下記プログラムになるのではないでしょうか？

using UnityEngine;

public class SwapTest : MonoBehaviour
{
    void Start()
    {
        int cupA = 10;  // コーラ
        int cupB = 20;  // オレンジジュース
        Debug.Log($"cupA={cupA} cupB={cupB}");

        Swap(cupA, cupB);

        Debug.Log($"cupA={cupA} cupB={cupB}");
    }

    private void Swap(int cupA, int cupB)
    {
        int emptyCup = cupA;
        cupA = cupB;
        cupB = emptyCup;
    }
}

ところがこのプログラムを実行した結果は次のようになります。

Swapメソッドを経由しても変数の中身が変わっていませんね。これは、Startメソッド内の変数と、Swapメソッドの引数に渡した変数が別物のため、Swapメソッド内の変数は入れ替わっているが、呼び出し元の変数には影響が及んでいません。

この問題を解決するには、呼び出したメソッドに対して、入れ替えで利用する変数を渡して上げる必要があります。これを実現するには「参照渡し」を利用する必要があります。

参照渡し込みのSwapメソッド

参照渡しを行うには、引数の型に「ref」を付けてあげることで解決です。変更したプログラムで実行結果を確認してみましょう。変更点はSwapメソッドとその呼出をしている行のみです。

using UnityEngine;

public class SwapTest : MonoBehaviour
{
    void Start()
    {
        int cupA = 10;  // コーラ
        int cupB = 20;  // オレンジジュース
        Debug.Log($"cupA={cupA} cupB={cupB}");

        Swap(ref cupA, ref cupB);

        Debug.Log($"cupA={cupA} cupB={cupB}");
    }

    private void Swap(ref int cupA, ref int cupB)
    {
        int emptyCup = cupA;
        cupA = cupB;
        cupB = emptyCup;
    }
}

この変更だけで、ちゃんとStartメソッドでの変数の値が交換されています。