2

In class today I had my students write (copy from textbook) a recursive Quick Sort in Python 3.2. I gave them a text file of 10,000 integers in reverse order (to illustrate worse case scenario). When students created a list of strings to sort, their code worked properly. If a student used a list of integers (converted from the text file input), their code crashed with a maximum recursion depth exceeded error. Any thoughts on why using a list of integers causes these results?

FYI - I could change a student's code from int to string lists, and vice versa, and consistently recreate the problem.

Improve this question
4
  • 4
    Is the recursive function calling int on the values, or are the values converted to int() first, then sorted? Commented Feb 4, 2014 at 16:03
  • Does this occur with other Python versions? Commented Feb 4, 2014 at 16:09
  • to check the answer below, you can use import sys sys.setrecursionlimit(10000), or higher, to see if you ever reach your base cases and it is simply worst case recursion. See this link Commented Feb 4, 2014 at 16:27
  • Thank you all for your thoughts. To clarify, we are reading a line from a text file (representing a single integer). We then append each line to a list which starts off empty. If we use strings, we strip the '\n' before appending to the list. If we use int, then we int() the string and then append it to the list. So this is the long way to say we int() it before we start sorting. I have not tried other versions of Python. I did try the sys.setrecursionlimit(10000), but it crashed the shell. Commented Feb 4, 2014 at 18:51

1 Answer 1

Reset to default
8

Let me guess: the file looked like

10000
9999
9998

etc. The sorted order of these strings is lexicograpic, and therefore different from that of the integers they represent:

>>> sorted(x)
['10000', '9998', '9999']
>>> sorted(x, key=int)
['9998', '9999', '10000']

According to the int order, the array is thus reverse-sorted, giving the worst-case performance for quicksort. But in the lexicographic order, it's quite far from reverse sorted; the completely naive quicksort that I just wrote up reaches a maximum recursion depth of only 130 on the input map(str, range(1, 10001)). Obviously, it does blow up on range(1, 10001) without Sedgewick's tail recursion optimization because the required recursion depth is then exactly 10000.

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

5 Comments

Why would this cause a 'recursion depth exceeded' error? Sure it might affect the sort order, but doesn't explain why something would break.
@Xymostech Added an explanation.
Ahh, good point sir! I suppose this is why it is sometimes beneficial to choose a random element as the "pivot".
A great thought and something to be aware of. This is not the case for this code, though, as I have checked both results using string and int in a small list and both are sorted correctly. To clarify, the 10,000 integers are generated by Python and are in the range 1 - 100,000. Interestingly, if I use the list as generated (random order), then both string and int versions work fine. I get the error when I use the int version with the original list in reverse (descending) order AND when it is in ascending order. Our Quick Sort should be sorting in ascending order.
@SteveH In that case you need to post example code and data to prevent this becoming a guessing game.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.