バブル・挿入・クイックソートをC言語で動かし直して測った

2026年11月改訂： この記事は2021年に韓国語で書いた講座を、日本語で書き直したものです。3つの例を Apple clang 21（Apple M1 Pro）でコンパイルし直して動かしました。バブルソートの例は出力が記事と違い（数字の間に空白がない）、クイックソートはランダムな配列20万個では正しかったものの、ソート済みの30万個を入れるとスタックオーバーフローで落ちました。 原因、修正したコード、速度の実測を加えています。

ソートとは

ソートは、データを決まった基準で順番に並べ直すことです。クラスの生徒を背の順に並べたり、本をタイトル順に並べたりするのもソートです。データがソートされていれば、二分探索のような速い検索が使えます。

バブルソート

バブルソートは、隣り合う2つを比べて、順番が逆なら入れ替える方法です。大きい値が泡のように後ろへ浮かんでいくので、この名前があります。

バブルソート

図では、まず84と69を比べて入れ替え、次に84と76を入れ替え、86のほうが大きいので84はそのままです。1周するたびに残りの最大値が末尾に決まるので、比較の範囲は1つずつ減っていきます。

比較回数 = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2

2021年の記事では、1万個で49,995,000を「交換回数」と書いていましたが、これは比較回数です。実際に数えた結果です（n = 10,000）。

元の記事は「交換が起きなくなったらループを抜ける」と説明していましたが、例のコードには早期終了がありませんでした。 最後の行のように、1周で交換がなければ止めると、ソート済みの入力は9,999回の比較で終わります。計算量はO(n²)で、早期終了があれば最良の場合はO(n)です。

void BubbleSort(int DataArray[], int Length)
{
    for (int i = 0; i < Length - 1; i++)
    {
        int swapped = 0;                              /* 2026: 早期終了を追加 */
        for (int j = 0; j < Length - (i + 1); j++)
        {
            if (DataArray[j] > DataArray[j + 1]) {
                int temp = DataArray[j + 1];
                DataArray[j + 1] = DataArray[j];
                DataArray[j] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;                          /* 交換なし＝ソート済み */
    }
}

2021年の例の出力バグ

元の例は printf("%d", DataArray[i]) で出力していて、数字の間に区切りがありませんでした。記事には 2 3 4 5 7 とありましたが、実際の出力はこうです。

$ printf "5\n7 5 4 3 2\n" | ./bubble
...: 23457

printf("%d ", DataArray[i]) にすれば直ります。malloc で確保した配列は free(DataArray); で解放しましょう。

挿入ソート

挿入ソートは、まだ並んでいないデータを1つずつ取り出し、すでに並んだ前の部分の適切な位置に差し込む方法です。手札のカードを並べるやり方と同じです。

1. 3と4を比べる。4が大きいのでそのまま
2. 4と6を比べる。そのまま
3. 6と2を比べる。2を取り出して3の前に入れる
4. 6と8を比べる。そのまま
5. 8と1を比べる。1を取り出して2の前に入れる

最良の場合O(n)（ソート済み）、平均と最悪はO(n²)です。平均の比較回数は約n(n-1)/4でバブルソートより少なく、下の計測でも約5倍速くなりました。

void InsertionSort(int arrData[], int Length)
{
    for (int i = 1; i < Length; i++)
    {
        int key = arrData[i], j = i - 1;
        while (j >= 0 && arrData[j] > key) {          /* 大きい値を1つずつ後ろへ */
            arrData[j + 1] = arrData[j];
            j--;
        }
        arrData[j + 1] = key;                         /* 空いた場所に入れる */
    }
}

2021年の例は正しく動きましたが、出力用の関数がコンパイラーの警告を出しました。

void PrintArray(int arrData[], int Length)
{
    for (int i = 0; i < Length; i++)
        printf("%d ", arrData[i]);
        printf("\n");          /* forの中にあるように見えるが、違う */
}

warning: misleading indentation; statement is not part of the previous 'for'

動作は意図どおり（最後に1回改行）ですが、インデントが読み手をだましています。for と揃えるか、波かっこを使いましょう。

クイックソート

クイックソートは分割統治法です。ピボットを1つ選び、それより小さい値を左、大きい値を右に分け、分かれた両方に同じことを繰り返します。

1. 5をピボットに選び、小さい値は左、大きい値は右に置く
2. 左側で4をピボットに選び、同じことをする
3. 右側で8をピボットに選び、同じことをする

平均の計算量はO(n log n)、最悪はO(n²)です。

2021年の実装（先頭の要素をピボットに使う）は次のとおりです。

int Partition(int numbers[], int left, int right)
{
    int first = left;
    int pivot = numbers[first];          /* 先頭の要素がピボット */
    int temp = 0;
    ++left;
    while (left <= right)
    {
        while (numbers[left] <= pivot && left < right) ++left;
        while (numbers[right] > pivot && left <= right) --right;
        if (left < right) {
            temp = numbers[left]; numbers[left] = numbers[right]; numbers[right] = temp;
        }
        else break;
    }
    temp = numbers[first]; numbers[first] = numbers[right]; numbers[right] = temp;
    return right;
}

void QuickSort(int numbers[], int left, int right)
{
    if (left < right)
    {
        int index = Partition(numbers, left, right);
        QuickSort(numbers, left, index - 1);
        QuickSort(numbers, index + 1, right);
    }
}

正しいか？ 20万回の検証

長さ0〜50、値の範囲を狭くして重複を多くしたランダムな配列を20万個ソートし、Cの標準 qsort の結果と比べました。不一致は0件で、この実装は正しく動きます。

問題はソート済みの入力

先頭の要素をピボットにすると、ソート済みの配列では毎回ピボットが最小値になります。片側が空になり、もう片側にn-1個が残るので、処理はO(n²)、再帰の深さもnになります。

再帰の深さがnだと、スタックがあふれることがあります。スタックの上限8MBで、ソート済みの配列を実際に試しました。

-O2 で生き残ったのは、コンパイラーが最後の再帰呼び出しをループに置き換える末尾呼び出し最適化をしたからです。同じコードがデバッグビルドでは落ち、リリースビルドでは動く。いちばん見つけにくい種類のバグです。

修正したクイックソート

2つ変えました。真ん中の要素をピボットにし（先頭と入れ替えてから既存の Partition をそのまま使う）、小さい側だけを再帰して大きい側はループで処理します。これで再帰の深さは最大でlog₂nに抑えられます。

void QuickSortFixed(int numbers[], int left, int right)
{
    while (left < right)
    {
        int mid = left + (right - left) / 2;               /* 真ん中の要素をピボットに */
        int t = numbers[left]; numbers[left] = numbers[mid]; numbers[mid] = t;
        int index = Partition(numbers, left, right);
        if (index - left < right - index) {                /* 小さい側だけ再帰 */
            QuickSortFixed(numbers, left, index - 1);
            left = index + 1;
        } else {
            QuickSortFixed(numbers, index + 1, right);
            right = index - 1;
        }
    }
}

修正版もランダムな配列20万個の検証で不一致0件でした。悪い入力での違いは次のとおりです。

3つのソートの速度比較（実測）

ランダムな整数、clang -O2、Apple M1 Pro。

データが10倍になると、挿入ソートは約96倍（O(n²)なら理論上100倍）、クイックソートは約13倍（O(n log n)）になりました。バブルソートは約330倍と理論値よりずっと大きく増えました（原因は分析していません。1万個の0.027秒という値が小さく、誤差が大きいこともあります）。qsort が手書きのクイックソートより少し遅いのは、比較関数をポインター経由で呼ぶコストのためです。

実務では

• ライブラリを使いましょう。Cは qsort、C++は std::sort、Pythonは sorted()/list.sort()、C#は Array.Sort/List.Sort。最悪の入力や再帰の深さの問題はすでに解決されています（std::sort は一般にイントロソート）。
• 自分で書くのは仕組みを学ぶためです。書くなら、ソート済み・逆順・重複の多い入力で必ず試し、デバッグビルド（-O0）でも動かしてください。
• ほぼ並んだ小さなデータでは挿入ソートが意外に速いので、多くの標準ライブラリは小さな範囲で挿入ソートに切り替えています。