pythonの辞書におけるvalueのマージソート

Question

pythonの辞書におけるvalueのソートに関してです。
以下の辞書のvalueでマージソートするプログラムを教えていただきたいです。（sortやsortedを使用せずにソートしたいです）
マージソートはマージソートの参照を参照して、プログラムを作成しています。
現在、valueのみのリストを作成し、valueのリストのソートはできているのですが、keyと分離しているため、希望する出力になりません。（プログラムのマージソートのの部分は参照先と同じものを使用しているため省略しています）
このような場合は、どのようにしてソートしたvalueともとの辞書のkeyを対応させるのでしょうか。
マージソートを使用して希望する出力が得られれば、他の方法でも問題ありません。

また、もし可能であれば、マージソートを降順にする方法も同時に教えていただけるとありがたいです。

point = {'A': 10, 'B': 29, 'C': 4, 'D': 10, 'E': 18, 'F': 4}

point_values = list(point.values())
print(merge_sort(point_values))

以下が現在の出力です。

[4, 4, 10, 10, 18, 29]

以下が希望する出力です。

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

Comments

[meg_]

・「安定ソート」とは質問においてどういう意味ですか？
・「valueでソートした場合、keyが対応しないため、詰まっています」 → valueのみのソートのコードを質問に追記してください。

[can110]

sortedを使いたくない理由はなんでしょうか？ （「じゃあlist.sort()で」という回答はOKですか？）
また「辞書のkeyとvalueを分離して、valueでソートした場合、keyが対応しないため」というのが理解できません。実際にそのように動くコードを書いて動かしたうえで、なんらかの不都合が生じたということでしょうか？

[LouiS0616]

とりあえず [int] のマージソートにトライしてみると良いと思います。
後からリストの中身を挿げ替えるのは案外簡単です。

[kawaramuu]

内容が伝わりにくく、大変申し訳ありません。修正して再投稿しましたが、もし不明点があればコメントいただけると助かります。よろしくお願いいたします。

[meg_]

「merge_sort()」のコードを提示いただかないと降順の方法も回答できないかと思います。

[kawaramuu]

marge_sort()の部分は参照先のマージソートと同じプログラムを使用させていただいています。先ほど，質問の内容を修正しました。何度も申し訳ありません。

Answer 1

希望の結果を見る限りはキー・値の組の値を見て降順ソートを行いたい、ということでしょうか。sortedのkey,reverse引数を活用すれば問題なくできるかと思います。

>>> from operator import itemgetter
>>> point = {'A': 10, 'B': 29, 'C': 4, 'D': 10, 'E': 18, 'F': 4}
>>> sorted(point.items(), key=itemgetter(1), reverse=True)
[('B', 29), ('E', 18), ('A', 10), ('D', 10), ('C', 4), ('F', 4)]

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

Comments

[kawaramuu]

回答いただき、ありがとうございます。先ほど、質問を修正しました。大変申し訳ありません。

Answer 2

リンク先のマージソートのコードを変更してみました。

def merge_sort_reverse(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    right = merge_sort_reverse(right)
    left = merge_sort_reverse(left)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge2(right, left)


def merge2(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(right) and r_i < len(left):
        # ここで=をつけることで安定性を保っている
        if right[l_i] >= left[r_i]:
            merged.append(right[l_i])
            l_i += 1
        else:
            merged.append(left[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(right):
        merged.extend(right[l_i:])
    if r_i < len(left):
        merged.extend(left[r_i:])
    return merged

print(merge_sort_reverse([1,2,3,4,5]))
#[5, 4, 3, 2, 1]

d = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5}
values = merge_sort_reverse(list(d.values()))

d2 = dict()

for value in values:
    for key in d:
        if d[key] == value:
            d2[key] = value

print(d2)
#{'E': 5, 'D': 4, 'C': 3, 'B': 2, 'A': 1}

Comments

[kawaramuu]

ありがとうございます！希望する出力を得ることができました。
質問の意図を上手く伝えれず，大変申し訳ありませんでした。

[hayataka2049]

値をソートして二重ループでキーを探して押し込む、斜め上の力技ですね！