ソートの安定性を調べるプログラム

安定なソートプログラムで必要なプログラム。
ゴチャゴチャするので別の記事として書き出してみました。

■プログラム is_stable.py

def is_stable(in_data, out_data):
    len_data = len(in_data)

    for i in range(len_data):
        for j in range(i+1, len_data):
            for a in range(len_data):
                for b in range(a+1, len_data):
                    if in_data[i][1] == in_data[j][1] and\
                       in_data[i] == out_data[b] and\
                       in_data[j] == out_data[a]:
                        return False

    return True

if __name__ == '__main__':
    # 実験1
    card1 = ['H1', 'S3', 'D1', 'C7', 'C1']
    card2 = ['D1', 'S3', 'H1', 'C7', 'C1']
    print(is_stable(card1, card2))
    
    # 実験2
    card1 = ['H1', 'S3', 'D1', 'C7', 'C1']
    card2 = ['H1', 'D1', 'C1', 'S3', 'C7']
    print(is_stable(card1, card2))

参考書「アルゴリズムとデータ構造」P.71の擬似プログラムをPythonでコーディングしただけです。

■実行結果

$ python is_stable.py
False
True

実験1では、card1の「H1→D1」という順序がcard2では「D1→H1」になってします。
そのため、不安定なソートということでFalseを表示しています。

一方、実験2では、同じ数字のカードの順序はそのままなので、Trueを表示します。

Pythonプログラミング物語 © 2016 Frontier Theme