ALDS1_2_C 安定なソートをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ALDS1_2_C 安定なソート」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
解答
感想
まとめ

問題文

トランプのカードを整列しましょう。ここでは、４つの絵柄(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）を出力してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_C

解答

#include <bits/stdc++.h>
using namespace std;

class card {
  public:
    char picture;
    int value;
};

void print_card(card c[], int n) {
    for(int i = 0; i < n; i++) {
        cout << c[i].picture << c[i].value;
        if(i != n - 1) {
            cout << " ";
        } else {
            cout << endl;
        }
    }
}

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

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

bool is_stable(card c1[], card c2[], int n) {
    bool stable = false;
    for(int i = 0; i < n; i++) {
        if(c1[i].picture == c2[i].picture && c1[i].value == c2[i].value) {
            stable = true;
        } else {
            stable = false;
            break;
        }
    }
    return stable;
}

int main() {
    int n;
    cin >> n;
    string cs[n];
    for(int i = 0; i < n; i++) {
        cin >> cs[i];
    }
    card c1[n], c2[n];

    for(int i = 0; i < n; i++) {
        c1[i].picture = cs[i][0];
        c1[i].value = cs[i][1] - '0';
        c2[i].picture = cs[i][0];
        c2[i].value = cs[i][1] - '0';
    }
    bubble_sort(c1, n);
    print_card(c1, n);
    cout << "Stable" << endl;

    for(int i = 0; i < n; i++) {
        c2[i].picture = cs[i][0];
        c2[i].value = cs[i][1] - '0';
    }
    selection_sort(c2, n);
    print_card(c2, n);
    if(is_stable(c1, c2, n)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }

    return 0;
}