クイックソートについて

Question

クイックソートについての質問です。Colaboratory python　を使用しています。

10人の国語と数学の合計を高い順に表示するためにクイックソートを作成しました。

def partition(nums, beginning, ending):
    i = beginning - 1
    pivot = nums[ending]
    for j in range(beginning, ending):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1], nums[ending] = nums[ending], nums[i + 1]
    return i+1

def quick_sort(nums, beginning, ending):
    if beginning < ending:
        pivot_index = partition(nums, beginning, ending)
        quick_sort(nums, beginning, pivot_index - 1)
        quick_sort(nums, pivot_index + 1, ending)
    return nums

続いて今回並び替えたいlistです

SeisekiList = [
{"NAMAE":"A ","KOKUGO":80,"SUGAKU":95},
{"NAMAE":"B","KOKUGO":75,"SUGAKU":75},
{"NAMAE":"C","KOKUGO":40,"SUGAKU":80},
{"NAMAE":"D","KOKUGO":60,"SUGAKU":60},
{"NAMAE":"E","KOKUGO":80,"SUGAKU":90},
{"NAMAE":"F","KOKUGO":95,"SUGAKU":95},
{"NAMAE":"G","KOKUGO":90,"SUGAKU":80},
{"NAMAE":"H","KOKUGO":75,"SUGAKU":85},
{"NAMAE":"I","KOKUGO":40,"SUGAKU":45},
{"NAMAE":"J","KOKUGO":80,"SUGAKU":60}
]

続いて実行前と実行後での比較しながら出力しようとしたところ、エラーが発生してしましました

for ent in SeisekiList:
  ent["GOKEI"]=ent["KOKUGO"]+ ent["SUGAKU"]

print("===Initial===")
for ent in SeisekiList:
  print("{:10s} {:>3d} {:3d} {:>3d}".format(ent["NAMAE"],ent["KOKUGO"],ent["SUGAKU"],ent["GOKEI"]))
quick_sort(SeisekiList,0, len(SeisekiList) - 1)
print("===Sorted===")
for ent in SeisekiList:
  print("{:10s} {:>3d} {:3d} {:>3d}".format(ent["NAMAE"],ent["KOKUGO"],ent["SUGAKU"],ent["GOKEI"]))

下記エラー内容です

TypeError                                 Traceback (most recent call last)
<ipython-input-10-d6677c2a86db> in <module>()
     22 for ent in SeisekiList:
     23   print("{:10s} {:>3d} {:3d} {:>3d}".format(ent["NAMAE"],ent["KOKUGO"],ent["SUGAKU"],ent["GOKEI"]))
---> 24 quick_sort(SeisekiList,0, len(SeisekiList) - 1)
     25 print("===Sorted===")
     26 for ent in SeisekiList:

1 frames
<ipython-input-10-d6677c2a86db> in quick_sort(nums, beginning, ending)
     11 def quick_sort(nums, beginning, ending):
     12     if beginning < ending:
---> 13         pivot_index = partition(nums, beginning, ending)
     14         quick_sort(nums, beginning, pivot_index - 1)
     15         quick_sort(nums, pivot_index + 1, ending)

<ipython-input-10-d6677c2a86db> in partition(nums, beginning, ending)
      3     pivot = nums[ending]
      4     for j in range(beginning, ending):
----> 5         if nums[j] <= pivot:
      6             i += 1
      7             nums[i], nums[j] = nums[j], nums[i]

TypeError: '<=' not supported between instances of 'dict' and 'dict'

どの部分を変えればエラーが発生せずに動くようになりますか？

Comments

[TakaiY]

発生したエラーも質問に載せていただけますか。
載せる場合、内容は最後の行だけでなく、すべてでお願いします。。

[waxaxaxa]

失礼いたしました。修正完了しました。

Answer 1

作成したソートは、「数値のリストを受け取って、その数値の順に並べ替える」ものであるのに対して、実際に与えているSeisekiListは、「辞書のリスト」だからでしょう。

クイックソートの方を、「dictのリストを受け取って、そのdictの指定されたキーの順に並べ替える」というものに変更すればいいのではないかと思います。
それほど大きな修正にはならないと思いますよ。

---

質問を受けて追記します。

ポイントは、今回比較したいのは、リストに入っているものそのものでなくて、その要素の1つであることです。

まず、quick_sort ()関数は、中に入っている数値の比較をしていないので、そのままでOKです。
1箇所している比較は、リストのインデックスですね。

実際に入れ替えをしているのは partition()関数の方ですね。

def partition(nums, beginning, ending):
    i = beginning - 1
    pivot = nums[ending]
    for j in range(beginning, ending):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1], nums[ending] = nums[ending], nums[i + 1]
    return i+1

ここで、 iとjは インデックスですから、そのままでいいのですね。
この中で比較している場所が1箇所、「nums[j] <= pivot」これです。このときの、nums[j] はリストの要素ですから、たとえば、{"NAMAE":"A ","KOKUGO":80,"SUGAKU":95, "GOUKEI", 175}のようなdictです。これそのものを比較したいものではありませんよね。 比較したいのは、さらにこの中の"GOUKEI"の値のはずです。なのでここは、「if nums[j]["GOUKEI"] <= pivot:」 としなければなりません。
また、ここで比較しているpivotは、この前で値を入れていますが、ここも「 pivot = nums[ending]["GOUKEI"]」のように目的の値を使うようにします。
基本的にこれで済むはずです。
他の部分も含めて考えてみてください。

さらに、ここでは、"GOUKEI"を直接使いましたが、関数の引数で受け取るようにして、quick_sort関数でも受け取るようにしてやれば、国語の成績でも、算数の成績でも並べ替えられるようにできますね。

Comments

[waxaxaxa]

回答ありがとうございます。返信遅れて申し訳ありません。ご回答いただいてから調べて試行錯誤したのですが、pythonを始めたばかりでよく理解できず、TakaiYさんがおっしゃっていた「dictのリストを受け取って、そのdictの指定されたキーの順に並べ替える」というのをどう表現したらいいかわかりませんでした。もしよければ一部で大丈夫ですので教えていただけると本当に助かります。

[waxaxaxa]

追加でのご回答ありがとうございます。無事実行して動くところまではできたのですが、出力の際”GOKEI”　の部分だけがソートされ、ほかの部分が動かないのですが合計が高い順に名前と国語数学も同時にならび変えるにはどうすればいいのでしょうか？

[TakaiY]

もしかして、「nums[i], nums[j] = nums[j], nums[i]」この部分などにも["GOUKEI"] を付けていませんか？
どこに付けてどこに付けるべきでないか、ようするに、何を比較して、何を入れ替えるか、を考えてみてください。