C++でバブルソート

アルゴリズムとデータ構造入門1_2

当記事について
ALDS1_2_A: Bubble Sort: バブルソート
1. 考えたことなど
2. コード例
おわり

当記事について

Aizu Online Judgeに掲載されている問題をC++で解くという遊びをしているので、考え方の例と解けたコード例を記録していこうかと思います。コード例はたたんでおこうかと思います。クリックやタップでコード例を開けます。

問題元はこちら:

Aizu Online Judge

ALDS1_2_A: Bubble Sort: バブルソート

バブルソートを実装する問題。実装が簡単で、$O(n^2)$の計算量で有名なアルゴリズムですね。

考えたことなど

擬似コードが与えられているので考えるようなこともないと思います。

値をチェックする流れと泡が浮かび上がる流れが重なっていて考えやすいアルゴリズムです。

C++はfor文で1列に出力するときに綺麗に書きづらいのが気になるなとは思いました。あと、std::cin >> aの標準入力から変数への格納は、改行だけでなく半角スペースでも区切られるようです。

あとから思いましたが、A->at(i)でなく、(*A)[i]使えばよかったです。>が比較に混じると視認性が落ちますね。

コード例

std::vector::reserveを予め領域確保のために使っていますが、格納される要素の最大個数$n$は、$0 \leq n \leq 100$なので行わなくてもいいと思います。

コード例は折り畳んであります。

// Bubble Sort

#include <iostream>
#include <vector>

int bubbleSort(std::vector<int> *A, int n);

int main()
{
    int n;
    std::vector<int> A;
    std::cin >> n;
    A.reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        int a;
        std::cin >> a;
        A.push_back(a);
    }
    int count = bubbleSort(&A, n);
    for (size_t i = 0; i < n; i++)
    {
        if (i != 0)
            std::cout << " ";
        std::cout << A[i];
    }

    std::cout << std::endl
              << count << std::endl;
}

int bubbleSort(std::vector<int> *A, int n)
{
    int count = 0;
    for (size_t i = 0; i < n; i++)
        for (size_t j = n - 1; i < j; j--)
            if (A->at(j) < A->at(j - 1))
            {
                std::swap(A->at(j), A->at(j - 1));
                count++;
            }
    return count;
}