寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C #ALDS1_2_C Stable Sort

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題
 トランプのカードを整列しましょう。
 ここでは、4つの絵柄(S, H, C, D)と9つの数字(1, 2, ..., 9)から構成される計 36 枚のカードを用います。
 例えば、ハートの 8 は"H8"、ダイヤの 1 は"D1"と表します。
 バブルソート及び選択ソートのアルゴリズムを用いて、与えられた N 枚のカードをそれらの数字を基準に昇順に整列するプログラムを作成してください。
 アルゴリズムはそれぞれ以下に示す疑似コードに従うものとします。数列の要素は 0 オリジンで記述されています。
f:id:neguse_atama:20200424123218p:plain
 また、各アルゴリズムについて、与えられた入力に対して安定な出力を行っているか報告してください。
 ここでは、同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにします。(※常に安定な出力を行うソートのアルゴリズムを安定なソートアルゴリズムと言います。)

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

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

・条件
   1 ≤ N ≤ 36

僕が作成、提出したコードは、以下のとおりです。

/*
 ALDS1_2_C Stable Sort
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct card{
    char suit;
    int value;
};
void BubbleSort(card A[],const int N){
    int flag=1;
    for(int i=0;flag;++i){
        flag=0;
        for(int j=N-1;i<j;--j)
            if(A[j].value<A[j-1].value){
                swap(A[j],A[j-1]);
                flag=1;
            }
    }
}
void SelectionSort(card A[],const int N){
    for(int i=0;i<N;++i){
        int min=i;
        for(int j=i;j<N;++j){
            if(A[j].value<A[min].value){
                min=j;
            }
        }
        if(i!=min){
            swap(A[i],A[min]);
        }
    }
}
int main(void){
    int N;
    scanf("%d%*c", &N);
    card A[N],B[N];
    for(int i=0;i<N;++i){
        scanf("%c%d%*c",&A[i].suit,&A[i].value);
        B[i]=A[i];
    }
    BubbleSort(A, N);
    SelectionSort(B, N);
    for(int i=0;i<N;++i){
        if(i>0){
            putchar(' ');
        }
        printf("%c%d",A[i].suit,A[i].value);
    }
    putchar('\n');
    printf("Stable\n");
    int flag=1;
    for(int i=0;i<N;++i){
        if(i>0){
            putchar(' ');
        }
        printf("%c%d",B[i].suit,B[i].value);
        if(!(B[i].suit==A[i].suit && B[i].value==A[i].value)){
            flag = 0;
        }
    }
    putchar('\n');
    if(flag){
        printf("Stable\n");
    }else{
        printf("Not stable\n");
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_2_C Stable Sort