Quiz
https://yukicoder.me/problems/no/397
ACコード
https://yukicoder.me/submissions/351014
その他
- バブルソートは関数化しておくと、今回のように交換したインデックスの組 (i, j) や、交換回数をカウントして反転数を求めるときに少し付け足すだけで済む
- O(N2)なので注意
void bubble_sort(vector<ll> &A){ ll N = A.size(); // iまで見る for(int i=N-1; i>=0; i--){ FOR(j, 0, i){ if(A[j] > A[j+1]){ swap(A[j], A[j+1]); } } } }
計算量
O(N2)