GRL_4_B: Topological Sort (続き3)

本来大小決められないあたりを適当に大小つけてるので
そのあたりにあやしいゾーンができてそうだってこと

調べる
成功するパターンから

コード

def sort(V):
    print([v.id for v in 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)
        print([v.id for v in V])

結果

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
[9, 5, 0, 1, 2, 3, 4, 8, 6, 7]
[9, 5, 7, 0, 1, 2, 3, 4, 8, 6]
[9, 5, 7, 2, 0, 1, 6, 3, 4, 8]
[9, 5, 7, 2, 4, 0, 1, 6, 3, 8]
[9, 5, 7, 2, 4, 8, 0, 1, 6, 3]
[9, 5, 7, 2, 4, 8, 3, 0, 1, 6]
[9, 5, 7, 2, 4, 8, 3, 6, 0, 1]
[9, 5, 7, 2, 4, 8, 3, 6, 0, 1]
[9, 5, 7, 2, 4, 8, 3, 6, 0, 1]

if文をこう書き換えると

            if V[j+1] < V[j]:

こう

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[2, 0, 1, 4, 3, 5, 9, 6, 7, 8]
[2, 4, 0, 1, 3, 5, 9, 7, 6, 8]
[2, 4, 0, 3, 1, 5, 9, 7, 6, 8]
[2, 4, 0, 3, 5, 1, 9, 7, 6, 8]
[2, 4, 0, 3, 5, 9, 1, 7, 6, 8]
[2, 4, 0, 3, 5, 9, 7, 1, 6, 8]
[2, 4, 0, 3, 5, 9, 7, 6, 1, 8]
[2, 4, 0, 3, 5, 9, 7, 6, 8, 1]
[2, 4, 0, 3, 5, 9, 7, 6, 8, 1]
[2, 4, 0, 3, 5, 9, 7, 6, 8, 1]

もっとこまかくprintする
最初のステップ

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
   [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
   [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
   [0, 1, 2, 3, 4, 5, 9, 6, 7, 8]
   [0, 1, 2, 4, 3, 5, 9, 6, 7, 8]
   [0, 2, 1, 4, 3, 5, 9, 6, 7, 8]
   [2, 0, 1, 4, 3, 5, 9, 6, 7, 8]
[2, 0, 1, 4, 3, 5, 9, 6, 7, 8]

これは合ってるの？

9は8や7や6よりは小さくて5とは大小決まらない
5と4は大小決まらない
4は3より小さくて2とは大小決まらない
2は1や0より小さい
書いたとおりだ（当然

でもバブルソートだから一番小さいものが一発で一番左にこないと変だよな
どれが一番小さいかは決められないけど
すくなくとも2が一番小さいということはない

            if V[j] > V[j+1]:

ではうまくいっている（ように見える）のに

            if V[j+1] < V[j]:

だとうまくいかないというのはなにか具体的な理由がある？

大小決まらないグレーゾーンの入り方が違うか
<(__lt__)はグレーゾーンがFalseになるけど
>(__gt__)はグレーゾーンがTrueになる
だから>のほうがswapされやすいってわけか

>なら100%OKとまではまだ言えてないと思うけど
先へ進んでもいいってくらいには納得した
ただ、バブルソートじゃなくなった途端うまくいかなくなるって
可能性は多大にある
組み込みのソートじゃだめだったし

バブルソートで間に合ってくれることを祈って進む