問題
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
数列 を読み込んで、昇順に並び変えて出力してね。
交換回数も出力してね。
制約
サンプル
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
考察
丁寧にやるだけ。
コード
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;
}