What is wrong with my python recursive quick sort algorithm?

Question

So my algorithm has two functions. The first is partition which takes the first element of the list as the pivot and places all elements larger than it after it and all the smallest before it and I have tested it and it works just fine. The second function quicksort function and it uses partition recursively to sort the entire list. When I run the code in pycharm it says maximum recursion depth exceeded and a few other errors. Here is the code:

arr = [81, 4, 73, 1, 98, 69, 300, 14, 7, 420, 190, 8, 9]


def partition(low, high):
    lo = low
    hi = high
    pivot = arr[lo]
    while lo < hi:
        while arr[lo] <= pivot:
            lo += 1
        while arr[hi] > pivot:
            hi -= 1
        if hi > lo:
            arr[lo], arr[hi] = arr[hi], arr[lo]
    arr[0], arr[hi] = arr[hi], arr[0]
    return hi


def quicksort(l, h):
    if l < h:
        j = partition(l, h)
        quicksort(l, j)
        quicksort(j + 1, h)


quicksort(0, 12)
print(arr)

P.S.: I'm a beginner (only 2 months of python) so please try to explain simply. Thanks in advance!

I just was told it must be used Perhaps you could ask the person who told you. — John Gordon
– John Gordon, Commented Nov 21, 2021 at 18:37
I doubt very much that your partition function works correctly. — user1984
– user1984, Commented Nov 21, 2021 at 18:57
just remove it and test your algorithm. If it has a purpose, a better choice than a constant 100000 would be max(arr)+1 because it is clearly meant to be larger than any array element. — RufusVS
– RufusVS, Commented Nov 21, 2021 at 18:59
User1984.. it works i tested it on its own. The errors are all to do with the recirsion part — theoneandonlysiuuuu
– theoneandonlysiuuuu, Commented Nov 21, 2021 at 19:00

score 1 · Accepted Answer · 2021-11-22 08:32:44Z

1

Your partition function is flawed. Also, you should make your functions more flexible/reusable by passing a reference to the list rather than working on a global variable. Here's my implementation using the Hoare algorithm and a different way to select the pivot:

def partition(A, lo, hi):
    pivot = A[(lo+hi)//2]
    i = lo - 1
    j = hi + 1
    while True:
        i += 1
        while A[i] < pivot:
            i += 1
        j -= 1
        while A[j] > pivot:
            j -= 1
        if i >= j:
            return j
        A[i], A[j] = A[j], A[i]


def quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)


arr = [81, 4, 73, 1, 98, 69, 300, 14, 7, 420, 190, 8, 9, 1, 2, 3, 9]
quicksort(arr, 0, len(arr)-1)
print(arr)

edited Nov 22, 2021 at 8:32

answered Nov 21, 2021 at 19:11

user2668284

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

2 Comments

theoneandonlysiuuuu Over a year ago

I dont get whats the big difference between my partition and yours. Whats the flaw? Try running it. Also, dumb question but does the return j statement make the program exit the infinite while loop?

user2668284 Over a year ago

Note how you have two "swaps" and yes, the return terminates the function returning the value of j. Try running my code

Collectives™ on Stack Overflow

What is wrong with my python recursive quick sort algorithm?

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