#5 - 文系出身エンジニアが競プロをやる

今日もアルゴリズムの本を読み進めながら、問題を解いていきます。

まずはじめに出てきたアルゴリズムはバブルソートです。
バブルソートは安定ソート（Stable Sort）です。

配列の末尾から隣接している要素を順番に比較し、求める順序へ置き換えていきます。

バブルソートはその名前が表すように、泡（Bubble）が水面に上がっていくように配列の要素が動いていきます。バブルソートは次のようなアルゴリズムで数列を昇順に並び変えます。

ALDS1_2_A: Bubble Sort

問題

数列 A を読み込み、バブルソートで昇順に並び変え出力するプログラムを作成してください。また、バブルソートで行われた要素の交換回数も報告してください。

入力

入力の最初の行に、数列の長さを表す整数 N が与えられます。２行目に、N 個の整数が空白区切りで与えられます。

出力

出力は 2 行からなります。１行目に整列された数列を 1 行に出力してください。数列の連続する要素は１つの空白で区切って出力してください。2 行目に交換回数を出力してください。

制約

・1 ≤ N ≤ 100
・0 ≤ A の要素 ≤ 100

コード

#include <iostream>

using namespace std;

void trace(int a[], int n) {
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << a[i];
    }
    cout << endl;
}

// bubble sort
int main() {
    int n;
    cin >> n;
    int r[n];

    for (int i = 0; i < n; i++) cin >> r[i];
    bool flag = true;
    int t, counter = 0;
    while (flag) {
        flag = false;
        for (int i = n - 1; i >= 1; i--) {
            if (r[i] < r[i - 1]) {
                t = r[i];
                r[i] = r[i - 1];
                r[i - 1] = t;
                counter++;
                flag = true;
            }
        }
    }

    trace(r, n);
    cout << counter << endl;
    return 0;
}

解説では、配列の先頭からソート済みと認識できると書かれていましたがこの実装は末尾からループを始めているので真逆ですね。
また要素の比較によって順番を入れ替えますが、等価だったケースは入れ替え処理を行わないので、前述した通り安定ソートとなります。

ちなみに、要素の入れ替えを地道にやっていますがswap関数をここで知りました。

反転数/転倒数

計算機科学および離散数学における列の転倒（てんとう、英: inversion）は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。

おわりに

選択ソート（selection sort）まで進めたんですが、時間が遅くなってしまったので次回書きたいと思います。
会社のSlackに競プロのチャンネルを作ったんですが、自分含めて16人いて嬉しいです。気合い入れていこう。