ソートアルゴリズムの比較

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

Sorting（ソート）は、データを一定の基準で配置する作業です。 数値の昇順だけでなく、体力、名前、生成時間など、複数の基準を使用できます。

選択ソート

残りの区間で最小値を求めて前方と変える。

for (int i = 0; i < Count - 1; ++i)
{
    int MinIndex = i;

    for (int j = i + 1; j < Count; ++j)
    {
        if (Values[j] < Values[MinIndex])
        {
            MinIndex = j;
        }
    }

    std::swap(Values[i], Values[MinIndex]);
}

実装は簡単ですが、比較回数O(N²)だから大きなデータには似合わない。

マージソート

配列を半分ずつ分け、それぞれ整列した後、合わせる。 時間の複雑さはO(N log N)安定したアライメントで実装できますが、合計は一時メモリを必要とします。

クイックソート

Pivotを基準に小さな値と大きな値を分け、各区間を並べ替えます。 平均はO(N log N)でも、ピボットの選択が悪い場合はO(N²)まで降りることができる。

実際のC ++コードでは、直接ソートを再作成するよりもstd::sortとstd::stable_sortを最初に使用します。

std::sort(Units.begin(), Units.end(),
    [](const Unit& A, const Unit& B)
    {
        return A.Speed > B.Speed;
    });

アルゴリズムを勉強して直接実装することと製品コードで検証された標準ライブラリを使用することは目的が異なります。