Python Quicksort Debugging

Question

I have implemented this quicksort but I seem to have bug that I can not fix, would someone mind taking a quick look at it?

The output for the example I give is close to the answer but some indices are misplaced.

def partition(array, pivot, start, end):

    # move pivot to the end
    temp = array[pivot]
    array[pivot] = array[end]
    array[end] = temp

    i = start
    j = end - 1 

    while(i < j):

        # check from left for element bigger than pivot
        while(i < j and array[end] > array[i]):
            i = i + 1
        # check from right for element smaller than pivot
        while(i < j and array[end] < array[j]):
            j = j - 1

        # if we find a pair of misplaced elements swap them
        if(i < j):
            temp = array[i]
            array[i] = array[j]
            array[j] = temp

    # move pivot element to its position
    temp = array[i]
    array[i] = array[end]
    array[end] = temp

    # return pivot position
    return i

def quicksort_helper(array, start, end):
    if(start < end):
        pivot = (start + end) / 2
        r = partition(array, pivot, start, end)
        quicksort_helper(array, start, r - 1)
        quicksort_helper(array, r + 1, end)

def quicksort(array):
    quicksort_helper(array, 0, len(array) - 1)

array = [6, 0, 5, 1, 3, 4, -1, 10, 2, 7, 8, 9]
quicksort(array)
print array

I have a feeling the answer will be obvious but I can not find it.

Desired output:

[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Actual output:

[-1, 0, 2, 3, 1, 4, 5, 6, 7, 8, 9, 10]

Yes, go obtain a rubber duck and it'll do the job. ericlippert.com/2014/03/05/how-to-debug-small-programs — jmoon
– jmoon, Commented Aug 16, 2017 at 21:07
So I probably should have mentioned that I have a similar solution that works where I change i < j to i <= j but I have had a hard time proving to myself that it is correct. I made it open ended like this so someone would give a detailed explanation as to why but I guess that backfired lol — Faramola J. Isiaka
– Faramola J. Isiaka, Commented Aug 16, 2017 at 21:26

Prune · Accepted Answer · 2017-08-16 21:49:38Z

1

The critical repair is in the inner while loops, where you march i and j toward each other. If all you're worried about is swapping the correct non-pivot elements, the logic you posted is fine. However, that first loop needs to be

    while(i <= j and array[end] > array[i]):
        i = i + 1

to ensure that i has the correct value for swapping the pivot element into the middle. Otherwise, you can swap it one element to the left of its proper position, which is why your sort fails.

You can also use Python's multiple assignment for a cleaner swap:

while(i < j):

    # check from left for element bigger than pivot
    while(i <= j and array[end] > array[i]):
        i = i + 1
    # check from right for element smaller than pivot
    while(i < j and array[end] < array[j]):
        j = j - 1

    # if we find a pair of misplaced elements swap them
    if(i < j):
        array[i], array[j] = array[j], array[i]

answered Aug 16, 2017 at 21:49

Prune

78k14 gold badges63 silver badges83 bronze badges

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

1 Comment

Faramola J. Isiaka Over a year ago

Preciate the answer bro, that made me understand and thanks for the multiple assignment tip I never knew that!

Collectives™ on Stack Overflow

Python Quicksort Debugging

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related