GRL_4_B: Topological Sort (続き2)

細かく見るのは明日にする

考えたけれどもわからない
組み込みのsortとかsortedではどう動いてるかわからないので
自前のバブルソートにしてみた
バブルソートにしたのは手抜きじゃなくて
ソートされてる様子がわかりやすいと思ったからだよ！

class Node():

    def __gt__(self, other):
        return not self < other and self is not other

def swap(V, x, y):
    tmp = V[x]
    V[x] = V[y]
    V[y] = tmp

def sort(V):
    for i in range(len(V)):
        for j in reversed(range(i, len(V) - 1)):
            if V[j] > V[j+1]:
                swap(V, j, j+1)

def main():
    nv, ne = [int(x) for x in input().split()]
    V = [Node(id) for id in range(nv)]
    read_edges(ne, V)
    sort(V)
    [print(v.id) for v in V]

そしたらcase#18までACで#19でTLE
これはこれで合ってるってことなのか・・・？
何も信用できなくなってきた

バブルソートだとよくて組み込みのソート（TimSortというらしい）では
ダメなのはなんだろう
TimSortはQuicksortなんかとはちがってStableらしいから
Stableかどうかで影響を受けるわけではないだろう
そもそも最初がバラバラなんだからStableかどうかは関係ないはず

さらに
気分的にif V[j] > V[j+1]:と書きかったので
__gt__を付け加えたんだけれども
if V[j+1] < V[j]:にすれば__lt__だけで済むよねと思って
やってみたら#14でWA
えーそうなの

gt、ltだけじゃなくてひととおり比較を実装したらなにか変わるかもと
思ってeq、ne、le、geも追加してみたけど結果は同じ
そもそもTimSortではltとeqしか呼ばれてない様子

le、geを書いてみて思ったのは
le = not gtとかge = not ltってわけじゃないとか
本来大小決められないあたりを適当に大小つけてるので
そのあたりにあやしいゾーンができてそうだってこと

でもわからないので
このままもう少し進めてみようかな