C - Stable Sort

cpaojalds1

最終更新日

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_C (新しいタブで開く)

問題文

バブルソートと選択ソートで、安定な出力をしているか判定してね。
「安定な出力」: 同じ数字を持つものが複数ある場合、ソート後も同じ順番になっていること。

制約

サンプル

I/O 1

5
H4 C9 S4 D2 C3

D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

I/O 2

2
S1 H1

S1 H1
Stable
S1 H1
Stable

考察

カードの柄がついてくれているので、安定ソートの判定は簡単。
あとは、バブルソートと選択ソートを実装するだけ。
コードは同じなので省略。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_2_C/judge/6745843/C++17 (新しいタブで開く)

typedef pair<string, int> P;

bool operator<(const P& lhs, const P& rhs) {
  return lhs.first[1] < rhs.first[1];
}
bool operator!=(const P& lhs, const P& rhs) {
  return lhs.first[1] != rhs.first[1];
}

vector<P> BubbleSort(vector<P> base) { ... }

vector<P> SelectionSort(vector<P> base) { ... }

void output(vector<P> bs) {
  rep(i, bs.size()) cout << bs[i].first << (i == bs.size() - 1 ? "\n" : " ");
  bool ok = true;
  rep(i, bs.size() - 1) {
    ok &= bs[i] != bs[i + 1] || bs[i + 1].second > bs[i].second;
  }
  puts(ok ? "Stable" : "Not stable");
}

int main() {
  int n;
  cin >> n;
  vector<P> cards(n);
  rep(i, n) {
    cin >> cards[i].first;
    cards[i].second = i;
  }
  output(BubbleSort(cards));
  output(SelectionSort(cards));
  return 0;
}