３．５ 安定なソート

説明に従って愚直にコーディング。

#include <iostream>
#include <algorithm>
#include <array>

using namespace std;

struct Card {
  char suit;
  int value;
  bool operator==(const Card& rhs) const {
    return this->suit == rhs.suit && this->value == rhs.value;
  }
};

static void printCard(Card cards[], int N) {
  for (int i = 0; i < N; i++) {
    cout << (i != 0 ? " " : "") << cards[i].suit << cards[i].value;
  }
  cout << endl; 
}

static void inputCard(Card cards[], int N) {
  for (int i = 0; i < N; i++) {
    cin >> cards[i].suit >> cards[i].value;
   }
}

static int bubbleSort(Card cards[], int N) {
  bool flag = true;
  int count = 0;
  for (int i =0; flag; i++) {
    flag = false;
    for (int j = N - 1; j > i; j--) {
      if (cards[j].value < cards[j - 1].value) {
        swap(cards[j], cards[j - 1]);
        flag = true;
        count++;
      }
    }
  }
  return count;
}

static int selectionSort(Card cards[], int N) {
  int minj, count = 0;
  for (int i = 0; i < N; i++) {
    minj = i;
    for (int j = i; j < N; j++) {
      if (cards[j].value < cards[minj].value) {
        minj = j;
      }
    }
    if (cards[i].value != cards[minj].value) {
      swap(cards[i], cards[minj]);
      count++;
    }
  }
  return count;
}

static bool isStable(Card in[], Card out[], int N) {
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      for (int a = 0; a < N; a++) {
        for (int b = a + 1; b < N; b++) {
          if (in[i].value == in[j].value && in[i] == out[b] && in[j] == out[a]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

int main() {
  int N;
  cin >> N;

  array<Card, 36> A, B;
  inputCard(A.data(), N);

  B = A;
  bubbleSort(B.data(), N);
  printCard(B.data(), N);
  bool stable;
  stable = isStable(A.data(), B.data(), N);
  cout << (stable ? "Stable" : "Not stable") << endl;
  
  B = A;
  selectionSort(B.data(), N);
  printCard(B.data(), N);
  stable = isStable(A.data(), B.data(), N);
  cout << (stable ? "Stable" : "Not stable") << endl;
  
  return 0;
}

だいぶ長くなりました。オンラインジャッジはなかなか正解にならず、じーっと見比べたところ、"Not stable " とするべきところを"Not Stable" としてしまっているのに気づきませんでした。こういうミスをなくしていきたい。

「バブルソートは常に安定」を反映すると、下記のようになります。（変更部分のみ抜粋）

static bool isSame(Card in[], Card out[], int N) {
  for (int i = 0; i < N; i++) {
    if (!(in[i] == out[i])) {
      return false;
    }
  }
  return true;
}

int main() {
  int N;
  cin >> N;

  array<Card, 36> A, B;
  inputCard(A.data(), N);

  B = A;
  bubbleSort(A.data(), N);
  selectionSort(B.data(), N);
  
  // バブルソートは常に stable.
  printCard(A.data(), N);
  cout << "Stable" << endl;

  // バブルソートと同じ結果か？
  printCard(B.data(), N);
  bool stable = isSame(A.data(), B.data(), N);
  cout << (stable ? "Stable" : "Not stable") << endl;
  
  return 0;
}

operator== を使いまわしています。まあ operator!= を定義しても良かったのですが。。