pythonでの辞書におけるソートアルゴリズム

Question

pythonでの辞書におけるソートのアルゴリズムに関してです。
以下のプログラムにおいて、valueでソートした場合、次の結果が出力されます。

point = {'A': 10, 'B': 29, 'C': 4, 'D': 10, 'E': 18, 'F': 4}
point_sorted = sorted(point.items(), key=lambda x:x[1], reverse=True)
print(point_sorted)

[('B', 29), ('E', 18), ('A', 10), ('D', 10), ('C', 4), ('F', 4)]

例えば、keyがAとDのvalueは同じ10ですが、ソート結果はAの方が先にあります。
これは元の辞書がA→Dの順のためと思うのですが、具体的なアルゴリズムを知りたいです。
初歩的な質問かもしれませんが、よろしく願いいたします。

Answer 1

sortedが利用している具体的なソートアルゴリズムは分かりませんがTimSortが採用されており、その結果が安定＝元の要素の順番を維持することは保証されています。詳細は以下を参照ください。

ソートの安定性と複合的なソート

ソートは、 安定 (stable) であることが保証されています。これはレコードの中に同じキーがある場合、元々の順序が維持されるということを意味します。

（略）
Python では Timsort アルゴリズムが利用されていて、効率良く複数のソートを行うことができます、これは現在のデータセット中のあらゆる順序をそのまま利用できるからです。

また、他に順序を維持するソートアルゴリズムにはどのようなものがあるかについては安定ソートを参照ください。

Comments

[LouiS0616]

TimSortが使われているみたいです。

> Python では Timsort アルゴリズムが利用されていて、効率良く複数のソートを行うことができます
https://docs.python.org/ja/3.9/howto/sorting.html#sort-stability-and-complex-sorts

[can110]

あ、ちゃんと書いてましたね。情報ありがとうございます。

[kawaramuu]

回答いただき、ありがとうございます！

Answer 2

まず、最近のPython（言語仕様としては3.7以降）では辞書の要素をdict.itemsで取得した場合、最初に書いた通りの順番で返ります。
（この書き方はちょっと語弊があるかもしれません。ドキュメントには「挿入順序」と書かれています。リテラルで定義した場合はその順序が保持され、かつ追加された要素は後ろに増えていくといったところでしょうか）

組み込み型 — Python 3.8.1 ドキュメント

あとはcan110さんの回答の通り安定ソートによってこの順序が保たれたままソートされます。

Python3.5以前では異なった挙動になるかもしれないので、多少の注意が必要です。

Comments

[kawaramuu]

回答いただき、ありがとうございます！