誰が一番速い？ソートアルゴリズムのスピード対決！

プログラム

はじめに

こんにちは。新人エンジニアのケンティーです。
今回は、プログラミングを学ぶ上で誰もが一度は通る「ソートアルゴリズム」の世界を少し掘り下げてみたいと思います。
世の中にはさまざまなソートアルゴリズムがありますが、「結局どれが一番速いの？」と気になったことはありませんか？
というわけで今回は、5つのソートアルゴリズムたちにスピード対決をしてもらいます！

ソートアルゴリズムとは…

ソートアルゴリズムとは、データを一定の基準で並べ替えるための方法のことを指します。
ゲームプログラミングにおいては、オブジェクトの描画順の制御やキャラをレア度や入手順で並べ替える機能など、様々な場面でソート処理が使われています。
一口に「ソート」と言っても、そのアルゴリズムは無数に存在し、計算量や安定性といった特性がそれぞれ異なります。

計算量とは…
アルゴリズムが処理を完了するまでに必要な計算の回数や時間の目安を表す指標です。
データの件数を「n」としたときに、処理がどの程度増えるかを「O記法」で表します。
この値が小さいほど、データ量が増えても効率よくソートできるということになります。

安定性とは…
同じ値のデータが並んでいるときに、ソート前の順番がソート後でも変わらない性質です。
以下の例では、「レア度」が同じモンスターがいた場合、「No.」の順番が変わらないかどうかがポイントです。

「No.」順に並んだデータ

No. 名前 レア度
1 スライム ★★
2 ゴブリン ★
3 ドラゴン ★★★
4 フェアリー ★★

このデータを「レア度」でソートを実行すると…

安定なソートを施したデータ
「スライム」と「フェアリー」の「No.」の前後関係が保たれています。

No. 名前 レア度
2 ゴブリン ★
1 スライム ★★
4 フェアリー ★★
3 ドラゴン ★★★

不安定なソートを施したデータ
「スライム」と「フェアリー」の「No.」の前後関係が崩れてしまっていますね。

No. 名前 レア度
2 ゴブリン ★
4 フェアリー ★★
1 スライム ★★
3 ドラゴン ★★★

ソートの基本的な知識を理解したところで、今回エントリーしたソートアルゴリズムたちを紹介していきます。

エントリーナンバー１ 「挿入ソート」

整列済みの部分に対して、未整列の要素を適切な位置に挿入していくソートです。

特徴

  • 実装が容易で、小規模データのソートに向いている。
  • データが逆順の場合、計算時間は最悪ケースになる。
  • 安定なソートである（同じ値の要素の順序は変わらない）。
ケース 計算量（時間計算量）
最良計算時間 O(n)
最悪計算時間 O(n^2)
平均計算時間 O(n^2)

処理の流れ

  • 2, [0], 4, 3, 1
    整列済みの「2」と未整列の「0」を比較
    「0 ≦ 2」なので、「2」の前に「0」を挿入
  • 0, 2, [4], 3, 1
    整列済みの「0, 2」と未整列の「4」を比較
    「0 ≦ 2 ≦ 4」なので、「2」の後ろに「4」を挿入
  • 0, 2, 4, [3], 1
    整列済みの「0, 2, 4」と未整列の「3」を比較
    「0 ≦ 2 ≦ 3 ≦ 4」なので、「4」の前に「3」を挿入
  • 0, 2, 3, 4, [1]
    整列済みの「0, 2, 3, 4」と未整列の「1」を比較
    「0 ≦ 1 ≦ 2 ≦ 3 ≦ 4」なので、「2」の前に「1」を挿入
  • 0, 1, 2, 3, 4

実装例

template<class T>
void InsertionSort(std::vector<T>& data)
{
    for (int32_t i = 0; i < data.size() - 1; ++i)
    {
        // 昇順で並んでいれば処理をスキップ
        if (data[i] <= data[i + 1])
            continue;

        // 値を挿入
        for (int32_t j = 0; j < i + 1; ++j)
        {
            // 要素の入れ替え
            if (data[j] > data[i + 1])
                std::swap(data[j], data[i + 1]);
        }
    }
}

エントリーナンバー２ 「バブルソート」

隣り合う要素を比較して、入れ替える操作を繰り返していくソートです。

特徴

  • 最悪・平均ケースは遅く、実用性は低い。
  • 安定なソートである（同じ値の要素の順序は変わらない）。
ケース 計算量（時間計算量）
最良計算時間 O(n)
最悪計算時間 O(n^2)
平均計算時間 O(n^2)

処理の流れ

  • [2, 0], 4, 3, 1
    隣り合う「2」と「0」を比較
    「2 ＞ 0」なので、要素を交換
  • 0, 2, [4], 3, 1
    最大値「4」を末尾に移動していく
  • 0, 2, [3], 1, 4
    次の最大値「3」を末尾に移動していく
  • 0, [2], 1, 3, 4
    次の最大値「2」を末尾に移動していく
  • 0, [1], 2, 3, 4
    次の最大値「1」は既に末尾、ソート終了
  • 0, 1, 2, 3, 4

実装例

template<class T>
void BubbleSort(std::vector<T>& data)
{
    for (int32_t i = 0; i < data.size(); ++i)
    {
        for (int32_t j = 0; j < data.size() - (i + 1); ++j)
        {
            // 要素の入れ替え
            if (data[j] > data[j + 1])
                std::swap(data[j], data[j + 1]);
        }
    }
}

エントリーナンバー３ 「選択ソート」

配列から最小or最大値を探し、配列の先頭要素と入れ替えていくソートです。

特徴

  • バブルソートに似ているが、ループ内の１度の処理で交換する回数が最大1回。
  • バブルソートに比べて高速。
  • 不安定なソートである(同じ値の要素の順序が変わる)。
ケース 計算量（時間計算量）
最良計算時間 O(n^2)
最悪計算時間 O(n^2)
平均計算時間 O(n^2)

処理の流れ

  • 2, [0], 4, 3, 1
    未確定部分の中の最小値「0」を未確定部分の先頭と交換
  • 0, 2, 4, 3, [1]
    未確定部分の中の最小値「1」を未確定部分の先頭と交換
  • 0, 1, [2], 4, 3
    未確定部分の中の最小値「2」を未確定部分の先頭と…
    既に先頭なので、交換しない
  • 0, 1, 2, 4, [3]
    未確定部分の中の最小値「3」を未確定部分の先頭と交換
  • 0, 1, 2, 3, 4

実装例

template<class T>
void SelectionSort(std::vector<T>& data)
{
    for (int32_t i = 0; i < data.size(); ++i)
    {
        int32_t minIdx = i;
        for (int32_t j = i + 1; j < data.size(); ++j)
        {
            // 最小値のインデックスを更新
            if (data[j] <= data[minIdx])
                minIdx = j;
        }

        // 要素の入れ替え
        if (i != minIdx)
            std::swap(data[i], data[minIdx]);
    }
}

エントリーナンバー４ 「クイックソート」

ピボットという基準となる値で配列を分割する操作を繰り返していくソートです。

特徴

  • 実装がやや複雑。
  • ピボットの選び方が適切でないと遅くなってしまう。
  • 不安定なソートである(同じ値の要素の順序が変わる)。
ケース 計算量（時間計算量）
最良計算時間 O(n log n)
最悪計算時間 O(n^2)
平均計算時間 O(n log n)

処理の流れ

  • 2, 0, 4, [3], 1
    ピボットを「3」と設定
    「3」を中心に小さいものを前に、大きいものを後ろに移動
  • 2, 0, [1], [3], 4
    「3」以前の中で、ピボットを「1」と設定
    「1」を中心に小さいものを前に、大きいものを後ろに移動
  • 0, [1], 2, 3, 4
    後ろの要素は1つしかないので、このまま確定
  • 0, 1, 2, 3, 4

実装例

template<class T>
void QuickSort(std::vector<T>& data, int32_t leftIdx, int32_t rightIdx)
{
    if (leftIdx < rightIdx)
    {
        // 基準値を基に要素を左右に分ける
        int32_t pivotIdx = Partition(data, leftIdx, rightIdx);

        // 左側の要素をソート
        QuickSort(data, leftIdx, pivotIdx - 1);

        // 右側の要素をソート
        QuickSort(data, pivotIdx + 1, rightIdx);
    }
}

template<class T>
int32_t Partition(std::vector<T>& data, int32_t leftIdx, int32_t rightIdx)
{
    // 3つのインデックスを昇順にソート
    int32_t indices[3] = {
        leftIdx,
        leftIdx + (rightIdx - leftIdx) / 2,
        rightIdx
    };
    if (data[indices[0]] > data[indices[1]]) 
        std::swap(indices[0], indices[1]);
    if (data[indices[1]] > data[indices[2]]) 
        std::swap(indices[1], indices[2]);
    if (data[indices[0]] > data[indices[1]]) 
        std::swap(indices[0], indices[1]);

    // 基準値を3つの要素の中央値に指定
    int32_t pivotIdx = indices[1];
    const T pivotValue = data[pivotIdx];

    // 基準値を右端に退避
    std::swap(data[pivotIdx], data[rightIdx]);

    // 基準値以下の要素を左側に集める
    int32_t storeIdx = leftIdx;
    for (int32_t i = leftIdx; i < rightIdx; ++i)
    {
        // 基準値より大きければ処理をスキップ
        if (data[i] > pivotValue)
            continue;

        // 要素を左側に移動
        if (i != storeIdx)
            std::swap(data[i], data[storeIdx]);
        ++storeIdx;
    }

    // 基準値を確定した位置に戻す
    pivotIdx = storeIdx;
    std::swap(data[pivotIdx], data[rightIdx]);

    return pivotIdx;
}

エントリーナンバー５ 「ボゴソート」

順番に並ぶまで、配列の要素をシャッフルし続けるソートです。

特徴

  • 実用性は皆無。
  • 最悪ケースでは、永遠にソートが終わらない。
  • 不安定なソートである(同じ値の要素の順序が変わる)。
ケース 計算量（時間計算量）
最良計算時間 O(n)
最悪計算時間 O(∞)
平均計算時間 O(n × n!)

処理の流れ

  • 2, 0, 4, 3, 1
    シャッフル！
  • 1, 3, 2, 4, 0
    シャッフル！
  • 3, 1, 0, 4, 2
    シャッフル！
    そろったので終了
  • 0, 1, 2, 3, 4

実装例

template<class T>
void BogoSort(std::vector<T>& data) final override
{
    // 昇順でソートできるまでループ
    while (!IsSorted(data))
    {
        // 「Fisher–Yates shuffle」アルゴリズムで要素をシャッフル
        for (int32_t i = data.size() - 1; i > 0; --i)
        {
            int32_t j = rand() % (i + 1);
            if (i != j)
                std::swap(data[i], data[j]);
        }
    }
}

template<class T>
bool IsSorted(const std::vector<T>& data)
{
    for (int32_t i = 0; i < data.size() - 1; ++i)
    {
        if (data[i] > data[i + 1])
            return false;
    }
    return true;
}

プログラムで速度を比較

さて、今回登場するソートアルゴリズムが出揃いました。
というわけで、各アルゴリズムを使用したソートプログラムで速度比較を行ってみましょう。
今回は、要素数１０の配列のソートを一万回実行し、平均タイムを算出しています。

結果は……

計測結果

アルゴリズム名 平均タイム(ms)
挿入ソート 0.0892
バブルソート 0.1127
選択ソート 0.0923
クイックソート 0.1252
ボゴソート 760680.0

ランキング

  1. 挿入ソート
  2. 選択ソート
  3. バブルソート
  4. クイックソート
  5. ボゴソート

考察

今回の計測では、比較的シンプルなソートである挿入ソート・選択ソート・バブルソートが、理論的に高速とされるクイックソートよりも良い結果を出しました。
この理由としては、データサイズの小ささと、アルゴリズムの実装オーバーヘッドの差にあると考えられます。

挿入ソート・選択ソート・バブルソートといった基本的なソートは、処理の流れが単純で、再帰呼び出しや複雑な分割操作を行いません。
関数呼び出しやピボット選択といった余分な処理が存在しない分、定数時間のオーバーヘッドが非常に小さいという特徴があります。
特に挿入ソートは、要素数が少ない場合において非常に効率的に動作し、メモリアクセスが連続的で無駄が少ないため、今回のような小規模なテストでは最も優れた結果を出したのだと考えられます。

一方で、クイックソートは理論上は高速ですが、今回のような小さな配列では、再帰処理やランダムピボットの選択といった処理コストが影響し、結果的に単純なアルゴリズムに劣る結果になったと考えられます。
というわけで、この考察が正しいのか今度は一位の挿入ソートとクイックソートを要素数１００の配列で再計測してみました。
結果はこちらです。

アルゴリズム名 平均タイム(ms)
挿入ソート 49.4666
クイックソート 8.4489

考察通り、データの規模によって得手不得手が明確に現れましたね。
忘れていましたが、ボゴソートは言わずもがなです。。。

まとめ

今回の結果から、アルゴリズムの性能はデータの規模や実装方法によって大きく変わることが分かりました。
小さなデータではシンプルなソートが強く、大きなデータでは複雑でも効率的なアルゴリズムが活躍します。
今後はプログラムを書くとき、「どんなデータを扱うのか」を意識してアルゴリズムを選んでいきたいと思います。

これにて、「ソートアルゴリズムのスピード対決」閉幕です！