Python Quicksort Runtime Error: Maximum Recursion Depth Exceeded in cmp

Question

I'm writing a program that will read a text file containing 5,163 names. (text file can be seen here)

Then I want to store the names into a list called 'names', afterwards, I sort the list based on how many letters the name contains, shorter names are at the start of the list and the longer ones are at the end.

I used quicksort to sort the list, but when I run it, it shows this error:

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

The full traceback is available as a pastie.

I've tested the quicksort function and it works for ordinary lists (ex: list = ['Alice','Bob,'Carl','Derp']), but it doesn't work if I try to sort 'names'

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

What's wrong with my code and how do I fix it?

@MartijnPieters yes, I know what `len(names)` does! I mean: how long is the list of names? — jonrsharpe, Aug 03 '14 at 14:25
@jonrsharpe: ah, I see what you mean; you want to know how deep the rabbit hole goes to produce that kind of stack trace. — Martijn Pieters, Aug 03 '14 at 14:26
jonrsharpe is correct: you are probably trying to sort **too large a list**. — Martijn Pieters, Aug 03 '14 at 14:27
Do you *have* to use Quicksort? Because the built-in sort is far superior to Quicksort, and you won't need to adjust it to avoid hitting the Python recursion limits. — Martijn Pieters, Aug 03 '14 at 14:30
The list contains 5,163 names, so len(names) should be 5,163 (if I didn't make a mistake that is) — DarkPotatoKing, Aug 03 '14 at 14:31
no I don't have to use quicksort, but I don't know how to modify the method of comparison if I use the built-in sort method — DarkPotatoKing, Aug 03 '14 at 14:32
Set e.g. `key=len` - see https://wiki.python.org/moin/HowTo/Sorting#Key_Functions — jonrsharpe, Aug 03 '14 at 14:33

score 18 · Accepted Answer · answered Aug 03 '14 at 14:33

18

You have simply hit the recursion limits. Your list of names is too large for Python's limited recursion capabilities. Your Quicksort works just fine otherwise.

You could raise the recursion limit by setting the limit higher with sys.setrecursionlimit(). You can set it a fair amount higher, but you do so at your own risk.

A better option is to use the built-in Python sort; the TimSort algorithm is far superior and won't hit a recursion limit:

names = sorted(names, key=len)

This sorts the names by their length, shortest names first.

answered Aug 03 '14 at 14:33

Martijn Pieters

1,048,767
296
4,058
3,343

What is a sane value for [`sys.setrecursionlimit()`](https://docs.python.org/2/library/sys.html#sys.setrecursionlimit)? – dhill Feb 05 '15 at 11:19
1

@dhill: The default is sane. If you need to raise it, think long and hard about the algorithm, perhaps it can be solved without recursion instead? – Martijn Pieters Feb 05 '15 at 11:37

score 9 · Answer 2 · edited May 23 '17 at 12:18

9

You exceed python default recursion size. The default recursion limit is 1000. You can increase recursion limit but it is not recommended. Here is how to do

import sys
sys.setrecursionlimit(1500)

Suggestion
My suggestion is use numpy.argsort() method which is already prepared for many sorting algorithms. Here is simple examle for how to do quicksort algorith by using numpy library.

edited May 23 '17 at 12:18

Community

1
1

answered Apr 13 '16 at 08:05

Harun ERGUL

5,770
5
53
62

Python Quicksort Runtime Error: Maximum Recursion Depth Exceeded in cmp

2 Answers2

Linked