Python Quicksort-Laufzeitfehler: Maximale Rekursionstiefe in cmp überschritten

Question

Aug 03, 2014, 04:14 PM

python runtime-error recursion quicksort

Python Quicksort-Laufzeitfehler: Maximale Rekursionstiefe in cmp überschritten

Ich schreibe ein Programm, das eine Textdatei mit 5.163 Namen liest. (Textdatei ist zu sehenHier)

Dann möchte ich die Namen in einer Liste namens "Namen" speichern, danach sortiere ich die Liste nach der Anzahl der Buchstaben, die der Name enthält, kürzere Namen am Anfang der Liste und die längeren am Ende.

Ich habe die Liste mit Quicksort sortiert, aber wenn ich sie ausführe, wird der folgende Fehler angezeigt:

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

Der vollständige Traceback ist verfügbarals Pastete.

Ich habe die QuickSort-Funktion getestet und sie funktioniert für normale Listen (z. B. list = ['Alice', 'Bob', 'Carl', 'Derp']), aber sie funktioniert nicht, wenn ich versuche, 'Namen' zu sortieren.

Hier ist mein Code

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()
#'''

Was ist los mit meinem Code und wie behebe ich ihn?

Zu kommentieren