C/C++アルゴリズム

バブルソート

各passで未整列部分の最大値が末尾へ移ります。

バブルソートとは？

各passで未整列部分の最大値が末尾へ移ります。

隣接する逆転を交換して整列します。

重要なポイント

空、1要素、重複、ソート済み入力をテストします。
正しさと最適化を分けます。
実務ではstandard libraryを優先します。

バブルソートのビジュアライザー

O(n²)

再生またはステップを使って、比較とデータ移動を順に確認できます。

CとC++のコード例

実行 →

main.c

#include <stdio.h>

int main(void) {
    int values[] = {5, 1, 4, 2};
    for (int end = 3; end > 0; --end) {
        int changed = 0;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                int temporary = values[index];
                values[index] = values[index + 1];
                values[index + 1] = temporary;
                changed = 1;
            }
        }
        if (!changed) break;
    }
    for (int index = 0; index < 4; ++index) {
        printf("%d ", values[index]);
    }
}

期待される出力

1 2 4 5

C++

実行 →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector values{5, 1, 4, 2};
    for (auto end = values.end(); end != values.begin(); --end) {
        bool changed = false;
        for (auto item = values.begin(); item + 1 != end; ++item) {
            if (*item > *(item + 1)) {
                std::iter_swap(item, item + 1);
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
}

期待される出力

1 2 4 5

CとC++の比較

学習向けでO(n²)です。早期終了でsorted inputはO(n)、実務C++では通常std::sortを使います。

loop、pointer、length、bufferを明示します。

C++

iteratorとalgorithmが操作と格納方法を分離します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

各比較を手で追跡します。
重複と極値をテストします。
standard libraryとbenchmarkします。