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

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

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

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

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

問題文

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

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

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

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

出力
1 行目に、バブルソートによって整列されたカードを順番に出力してください。隣合うカードは1つの空白で区切ってください。 2 行目に、この出力が安定か否か(Stable またはNot stable)を出力してください。 3 行目に、選択ソートによって整列されたカードを順番に出力してください。隣合うカードは1つの空白で区切ってください。 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;
}

感想

トランプのカードをソートする問題ですが、データ構造をどうするか迷いました。

上記コードよりもっとスマートな方法があると思いますが、現状の私の手段ではこのようなやり方になってしまいました。

クラスの設計方法としてはよくないと思います。

それとソートするために文字列の一部を数値に変換する処理があり、そこが新しい内容でしょうか。

バブルソートと選択ソートについては以前の問題にも出ている形を流用しています。

ソートするためのデータ構造を、前回の問題の配列からより難しくなった問題でした。

まとめ

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

以上です。
読んでいただきありがとうございました!