ALDS1_2_C: Stable Sort

問題だけ読んで、正解にしてから解説を読む、ってやったんですが
安定性の判断ってとこでけっこう悩みました
まず全部、値でグループを作ってから判定することにしました
C++だとどんなライブラリになるんだろうか、
今どきライブラリにもないってことはないだろう、などと思いつつ

#! /usr/local/bin/python3
# coding: utf-8

def swap(c, i, j):
    t = c[i]
    c[i] = c[j]
    c[j] = t

def bubble_sort(cs, f):
    c = cs[:]
    for i in range(len(c) - 1):
        for j in range(len(c) - 1, i, -1):
            if f(c[j - 1]) > f(c[j]):
                swap(c, j - 1, j)
            # print(i, j, c)
    return c

def selection_sort(cs, f):
    c = cs[:]
    for i in range(len(c)):
        minj = i
        for j in range(i, len(c)):
            if f(c[j]) < f(c[minj]):
                minj = j
        swap(c, i, minj)
        # print(c)
    return c

def to_group(c):
    b = {}
    for i in c:
        if not(i[1] in b):
            b[i[1]] = [i]
        else:
            b[i[1]] = b[i[1]] + [i]
    return b

def is_stable(c, s):
    bc = to_group(c)
    bs = to_group(s(c, lambda x: x[1]))
    # print(bc)
    # print(bs)
    for k in bc:
        if bc[k] != bs[k]:
            return "Not stable"
    return "Stable"

n = int(input())
c = input().split()

print(" ".join(bubble_sort(c, lambda x: x[1])))
print(is_stable(c, bubble_sort))

print(" ".join(selection_sort(c, lambda x: x[1])))
print(is_stable(c, selection_sort))

Stableかどうかの判定はどうやら動いてます

rangeが半開区間なのは理にかなってると思うんですが、減らしていきたいときは
あんまり直感的じゃないっていうか何度も間違えました

ひとつずつソートを実装して動かしてみてよしOK、と思って提出したらWAで
どうなってるのかと思って調べてたんですけど
本に載ってる擬似コードと微妙にループ回数が違う！とかいろいろやったあげく
cを使いまわしてたので最初のバブルソートでcがソートされて
その後は全部ソート済みのcをソートしてるということが発覚しました
まず複製作ってからからソートして返すってして通したんですけど
普通はどう書くものですかね

ていうかループ回数、おかしくない？と思ったら正誤表出てました
擬似コードはともかく、本物のコードの方も間違ってるのはマズくないですか
たまたまSegmentation Faultとか出なかった？

さて解説を見てみます
is_stableの部分

ソートの結果が安定かどうかを調べるには、Nの値が小さいので、次のようなカードの組に対する順番を愚直に調べるO(N⁴)のアルゴリズムを適用することができます。

それは考えもしなかったなあ
まずは愚直に、って考えるようにしてるつもりでしたが
N⁴となると愚直すぎたか
ディクショナリの中でN²分くらいがんばってくれてるかもしれないけど

しかし今日の衝撃はそこではなかった
バブルソートのStable判定のコード

cout << "Stable" << endl;

O(1)だった
まじすか
そして選択ソートのStable判定はバブルソートの結果との比較で出すという

そういうのもありなのね