[解決済み] Python Quicksort Runtime Error: cmp で最大再帰深度を超えました。

質問

5,163人の名前が入ったテキストファイルを読み込むプログラムを書いています。(テキストファイルは こちら )

その後、名前に含まれる文字数に基づいてリストをソートし、短い名前をリストの先頭に、長い名前をリストの末尾に配置したいと思います。

リストのソートにquicksortを使用しましたが、実行するとこのエラーが表示されます。

C:\Python27\python.exe C:/Users/Lenovo/Desktop/Anagrams/Main.py
Traceback (most recent call last):
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 25, in <module>
    names = quicksort(names)
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
# [.... many lines elided ...]
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 3, in quicksort
    if list == []:
RuntimeError: maximum recursion depth exceeded in cmp

完全なトレースバックが利用可能です パスティとして .

クイックソート機能を試してみたところ、普通のリスト（ex: list = ['Alice','Bob,'Carl','Derp'] ）ではうまくいきましたが、「名前」をソートしようとするとうまくいきません。

以下は私のコードです。

def quicksort(list):
    """Quicksort using list comprehensions"""
    if list == []:
        return []
    else:
        pivot = list[0]
        lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
        greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
        return lesser + [pivot] + greater

def lessThan(a, b):
    return len(a) < len(b)

#'''
input = open('Names.txt', 'r')
output = open('Names Arranged By Length.txt', 'w')

names = []

for line in input:
    line = line.translate(None, '\n')
    names.append(line)


names = quicksort(names)

for i in names:
    print i
    output.write(i)
    output.write('\n')

print 'Count: ', len(names)


input.close()
output.close()
#'''

私のコードのどこが悪くて、どう直せばいいのでしょうか？

どのように解決するのですか？

再帰の限界に達しただけです。名前のリストが大きすぎて、Pythonの限られた再帰処理機能しか使えないのです。Quicksortはそれ以外では問題なく動作します。

あなた できる で再帰回数の上限を高く設定することで、再帰回数の上限を上げることができます。 sys.setrecursionlimit() . かなり高く設定することも可能ですが、その場合は自己責任でお願いします。

より良い方法は、Pythonの組み込みソートを使用することです。 TimSortアルゴリズム ははるかに優れており、再帰の制限にぶつかることもない。

names = sorted(names, key=len)

これは、名前を長さの順にソートし、短い名前を先にします。