ALDS1_2_A バブルソートをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ALDS1_2_A バブルソート」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
解答
感想
まとめ

問題文

バブルソートはその名前が表すように、泡（Bubble）が水面に上がっていくように配列の要素が動いていきます。バブルソートは次のようなアルゴリズムで数列を昇順に並び変えます。
1 bubbleSort(A, N) // N 個の要素を含む 0-オリジンの配列 A
2 flag = 1 // 逆の隣接要素が存在する
3 while flag
4 flag = 0
5 for j が N-1 から 1 まで
6 if A[j] < A[j-1]
7 A[j] と A[j-1] を交換
8 flag = 1
数列 A を読み込み、バブルソートで昇順に並び変え出力するプログラムを作成してください。また、バブルソートで行われた要素の交換回数も報告してください。
入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。２行目に、N 個の整数が空白区切りで与えられます。
出力
出力は 2 行からなります。１行目に整列された数列を 1 行に出力してください。数列の連続する要素は１つの空白で区切って出力してください。2 行目に交換回数を出力してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_A

解答

#include <bits/stdc++.h>
using namespace std;

void print_array(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cout << a[i];
        if(i == n - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }
}

int bubble_sort(int a[], int n) {
    bool flag = true;
    int count = 0;
    while(flag) {
        flag = false;
        for(int i = n - 1; i >= 1; i--) {
            if(a[i] < a[i - 1]) {
                swap(a[i], a[i - 1]);
                flag = true;
                count++;
            }
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int count = bubble_sort(a, n);

    for(int i = 0; i < n; i++) {
        cout << a[i];
        if(i == n - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }
    cout << count << endl;

    return 0;
}