A - Bubble Sort

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_A

問題文

バブルソート。泡が水面に上がっていくイメージ。
疑似コードは以下の通り。

bubbleSort(A, N) // N 個の要素を含む 0-オリジンの配列 A
  flag = 1 // 逆の隣接要素が存在する
  while flag
    flag = 0
    for j が N-1 から 1 まで
      if A[j] < A[j-1]
        A[j] と A[j-1] を交換
        flag = 1

数列 $A$ を読み込んで、昇順に並び変えて出力してね。
交換回数も出力してね。

制約

• $1 \le N \le 100$
• $0 \le A_i \le 100$

サンプル

I/O 1

5
5 3 2 4 1

1 2 3 4 5
0

I/O 2

6
5 2 4 6 1 3

1 2 3 4 5 6
9

考察

丁寧にやるだけ。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_2_A/judge/6379632/C++17

int cnt = 0;

void bubbleSort(vector<int>& a, int n) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int j = n - 1; j > 0; --j) {
      if (a[j] < a[j - 1]) {
        swap(a[j], a[j - 1]);
        ++cnt;
        flag = true;
      }
    }
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  bubbleSort(a, n);
  rep(i, n) cout << a[i] << (i == n - 1 ? "\n" : " ");
  cout << cnt << endl;
  return 0;
}