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

昨日もそうでしたが、今朝は寝起きから信じられないぐらい頭痛でダメでした。さあ張り切ってプロコンをやっていきましょう。

今回は、昨日書ききれなかった選択ソート（Selection Sort）です。
この選択ソートは、実行を行った結果必ず要素の実行を行うため、安定ソート（Stable Sort）ではありません。

ALDS1_2_B: Selection Sort

比較的簡単なアルゴリズムです。

選択ソートは、各計算ステップで１つの最小値を「選択」していく、直観的なアルゴリズムです。

擬似コード

SelectionSort(A)
1 for i = 0 to A.length-1
2     mini = i
3     for j = i to A.length-1
4         if A[j] < A[mini]
5             mini = j
6     swap A[i] and A[mini]

問題文

数列Aを読み込み、選択ソートのアルゴリズムで昇順に並び替え出力するプログラムを作成してください。上の疑似コードに従いアルゴリズムを実装してください。
疑似コード 7 行目で、i と minj が異なり実際に交換が行われた回数も出力してください。

入力

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

出力

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

制約

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

コード（解答）

#include <iostream>
#include <algorithm>

using namespace std;
static const int MAX = 100;

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

// selection sort
int main() {
    int n, counter = 0, r[MAX];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> r[i];

    for (int i = 0; i < n - 1; i++) {
        int minj = i;
        for (int j = i; j < n; j++) {
            if (r[j] < r[minj]) minj = j;
        }
        swap(r[i], r[minj]);
        if (i != minj) counter++;
    }

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

簡単でした。0から要素の個数-1回が外側のループで、内側ではi...n-1の間で最小値を探していきます。外側のループを抜けた後に、入れ替えます。
楽しようとして、関数調べたりしましたが、愚直に書いて無事パスさせました。

ALDS1_2_C: Stable Sort

#5 で扱ったバブルソートと選択ソートの復習です。

バブルソートと選択ソートを実装して、それが安定かどうかを確認します。

if (bubbleSort) cout << "Stable" << endl;
if (selectionSort) cout << "Not stable" << endl;

擬似コード

1 BubbleSort(C, N)
2   for i = 0 to N-1
3     for j = N-1 downto i+1
4       if C[j].value < C[j-1].value
5         C[j] と C[j-1] を交換
6
7 SelectionSort(C, N)
8   for i = 0 to N-1
9     minj = i
10    for j = i to N-1
11      if C[j].value < C[minj].value
12        minj = j
13    C[i] と C[minj] を交換

問題文

トランプのカードを整列しましょう。ここでは、４つの絵柄(S, H, C, D)と９つの数字(1, 2, ..., 9)から構成される計 36 枚のカードを用います。例えば、ハートの 8 は"H8"、ダイヤの 1 は"D1"と表します。

バブルソート及び選択ソートのアルゴリズムを用いて、与えられた N 枚のカードをそれらの数字を基準に昇順に整列するプログラムを作成してください。アルゴリズムはそれぞれ以下に示す疑似コードに従うものとします。数列の要素は 0 オリジンで記述されています。

また、各アルゴリズムについて、与えられた入力に対して安定な出力を行っているか報告してください。ここでは、同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにします。（※常に安定な出力を行うソートのアルゴリズムを安定なソートアルゴリズムと言います。）

入力

1 行目にカードの枚数 N が与えられます。 2 行目に N 枚のカードが与えられます。各カードは絵柄と数字のペアを表す２文字であり、隣合うカードは１つの空白で区切られています。

出力

1 行目に、バブルソートによって整列されたカードを順番に出力してください。隣合うカードは１つの空白で区切ってください。
2 行目に、この出力が安定か否か（Stable またはNot stable）を出力してください。
3 行目に、選択ソートによって整列されたカードを順番に出力してください。隣合うカードは１つの空白で区切ってください。
4 行目に、この出力が安定か否か（Stable またはNot stable）を出力してください。

制約

・1 ≤ N ≤ 36

コード

#include <iostream>

using namespace std;

struct Card {
    char suit, value;
};

static const int MAX = 36;

void bubbleSort(struct Card card[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j >= i + 1; j--) {
            if (card[j].value < card[j - 1].value) {
                swap(card[j], card[j - 1]);
            }
        }
    }
}

void selectionSort(struct Card card[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minj = i;
        for (int j = i; j < n; j++) {
            if (card[minj].value > card[j].value) minj = j;
        }
        swap(card[minj], card[i]);
    }
}

bool isStable(struct Card c1[], Card c2[], int n) {
    for (int i = 0; i < n; i++) {
        if (c1[i].suit != c2[i].suit) return false;
    }
    return true;
}

void output(struct Card c[], int n) {
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << c[i].suit << c[i].value;
    }
    cout << endl;
}

int main() {
    Card c1[MAX], c2[MAX];
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> c1[i].suit >> c1[i].value;
    for (int i = 0; i < n; i++) c2[i] = c1[i]; // copied

    bubbleSort(c1, n);
    output(c1, n);
    cout << "Stable" << endl;

    selectionSort(c2, n);
    output(c2, n);
    if (isStable(c1, c2, n)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }
    return 0;
}

実を言うと、20分ぐらいでざっと実装したものがCompileError / RuntimeErrorでパスしなかったです。AOJの中身見てもRuntimeErrorの理由はわからなかったので解説を確認しつつコードを書き直しました。

以下に初回に書いたコードもコミットしています。

AOJ 2019/04/26 - 1 : stable sort by paveg 揃 Pull Request #1 揃 paveg/programming_contest

そして今回はstructが登場しました。普段良く書くRubyでは、あまりStructを使うことがないのですが、C++では便利なので積極的に使っていこうと思います（最初の実装では地道に配列見てますね…）。

isStable関数は O(N^4)のアルゴリズムを使っていますが、要素の数がより多い場合は、工夫が必要そうです。またバブルソートは安定ソートなので、有無を言わさずStableと吐いています。

選択ソートの計算量

選択ソートはデータがN個あるとして最小値を見つけるために、N-1 -> N-2 -> N-3,...と比較演算を実行します。そのため、演算の回数は
(N^2 - N)/2 となり、 計算量は N^2に比例してオーダーはO(N^2)となります。

おわりに

PjMとして参画していたプロジェクトがリリースを迎えたのでここで紹介させてください。

2019/04/25 freee株式会社とGMOあおぞらネット銀行
参照系APIの連携を開始 | お知らせ・プレスリリース

ちなみにGMOあおぞらネット銀行のAPI連携は、個人・法人の口座どちらも対応しています。めっちゃ便利なので使ってみてね。
これを機に俺も試してみようと思っています！

そしてそろそろGWですね。皆さんやることや行くところは決めましたか？
後少しで休みなので、金曜日も張り切っていきましょう💪💪💪