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
– jonrsharpe, Commented Aug 3, 2014 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
– Martijn Pieters, Commented Aug 3, 2014 at 14:26
jonrsharpe is correct: you are probably trying to sort too large a list. — Martijn Pieters
– Martijn Pieters, Commented Aug 3, 2014 at 14:27
Set e.g. key=len - see wiki.python.org/moin/HowTo/Sorting#Key_Functions — jonrsharpe
– jonrsharpe, Commented Aug 3, 2014 at 14:33

Martijn Pieters · Accepted Answer · 2014-08-03 14:33:59Z

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 3, 2014 at 14:33

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

dhill Over a year ago

What is a sane value for sys.setrecursionlimit()?

Martijn Pieters Over a year ago

@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?

Community · Accepted Answer · 2017-05-23 12:18:07Z

10

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, 2017 at 12:18

CommunityBot

11 silver badge

answered Apr 13, 2016 at 8:05

Harun ERGUL

5,9805 gold badges58 silver badges65 bronze badges

Collectives™ on Stack Overflow

Python Quicksort Runtime Error: Maximum Recursion Depth Exceeded in cmp

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related