Why do I have maximum recursion depth for Quick Sort in Python?

Question

I am trying to implement the quick sort based on a pseudocode I was given, and I understand how the algorithm works.
When I run a test on the function and the input list is randomized, it runs perfectly fine.
Yet, when I run a descending or ascending sorted list through the function I get the error of maximum recursion depth. To my understanding, it is because the pivot I chose was not randomized, as in inputs of elements 900 and under, the code works fine, but once I put 1000 elements for a list that is not randomized I receive that error. I am unsure how to go about randomizing it without using the rand function.
I also tried using the mid point, but my output is incorrect and I cannot figure out why.
Any help and explanation would be appreciated.

    def quicksort(self, query_list, left, right):
        if left < right:
            mid = self.partition(query_list, left, right)
            self.quicksort(query_list, left, mid - 1)
            self.quicksort(query_list, mid + 1, right)

    def partition(self, query_list, beg, end):
        pivot = query_list[end]
        i = beg - 1
        for j in range(beg, end):
            if query_list[j] >= pivot:
                i = i + 1
                (query_list[i], query_list[j]) = (query_list[j], query_list[i])
        (query_list[i + 1], query_list[end]) = (query_list[end], query_list[i + 1])
        return i + 1

Input a list rand: [3, 4, 8, 2, 0, 1]
Output: [8, 4, 3, 2, 1, 0]

I tried:

mid = (beg + end) // 2
pivot = query_list[mid]

My results:
Input list at random: [8, 2, 4, 1, 9, 3, 7, 10, 6, 5]
Output: [10, 9, 8, 6, 7, 1, 4, 3, 5, 2]

wiki page describes "median of three" method to choose pivot and gives some words about optimization due to partial or full recursion elimination. I'd recommend to look in Sedgewick Algorithms book. — MBo
– MBo, Commented Oct 3, 2022 at 8:41
Check what return values you are getting from your partition function. — khelwood
– khelwood, Commented Oct 3, 2022 at 8:45
When selecting query_list[end] for pivot, the pivot gets swapped with the value at the index returned. What is the value there when you choose query_list[mid]? — greybeard
– greybeard, Commented Oct 3, 2022 at 10:03
With a sorted list, your pivot pick query_list[end] will always give you one empty partition and one partition containing the rest of the array. That is maximally inefficient, hence the maximum recursion depth. As @MBo suggested, using 'median of three' will give better results. — rossum
– rossum, Commented Oct 3, 2022 at 14:31

rcgldr · Accepted Answer · 2022-10-04 21:39:12Z

1

To use middle element as pivot with the Lomuto partition scheme used in the question, swap middle element with last element:

    def partition(self, query_list, beg, end):
        mid = (beg+end)/2
        query_list[mid],query_list[end] = query_list[end],query_list[mid]
        pivot = query_list[end]

edited Oct 4, 2022 at 21:39

answered Oct 4, 2022 at 20:49

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

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

2 Comments

Karl Knechtel Over a year ago

"with the Lomuto partition scheme used in the question" What are you referring to? I don't see anything like that in the OP.

rcgldr Over a year ago

@KarlKnechtel - Hoare used 2 indexes, one scans left to right, the other right to left. Lomuto uses a single index that scans left to right.

Collectives™ on Stack Overflow

Why do I have maximum recursion depth for Quick Sort in Python?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related