A - Bubble Sort

cpaojalds1

最終更新日

Table of Contents

Loading...

問題

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

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

制約

サンプル

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; }