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.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
SteveH
  • 21
  • 1
  • 4
    Is the *recursive function* calling `int` on the values, or are the values converted to `int()` first, then sorted? – Martijn Pieters Feb 04 '14 at 16:03
  • Does this occur with other Python versions? – Markus Unterwaditzer Feb 04 '14 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](http://stackoverflow.com/questions/8177073/python-maximum-recursion-depth-exceeded) – C.B. Feb 04 '14 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. – SteveH Feb 04 '14 at 18:51

1 Answers1

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 3
    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 Feb 04 '14 at 16:07
  • @Xymostech Added an explanation. – Fred Foo Feb 04 '14 at 16:11
  • Ahh, good point sir! I suppose this is why it is sometimes beneficial to choose a random element as the "pivot". – mgilson Feb 04 '14 at 16:13
  • 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 Feb 04 '14 at 19:00
  • 1
    @SteveH In that case you need to post example code and data to prevent this becoming a guessing game. – Fred Foo Feb 04 '14 at 22:03