バブルソート

Quiz

https://yukicoder.me/problems/no/397

ACコード

https://yukicoder.me/submissions/351014

その他

• バブルソートは関数化しておくと、今回のように交換したインデックスの組 (i, j) や、交換回数をカウントして反転数を求めるときに少し付け足すだけで済む
• O(N²)なので注意

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(N²)