Implementing QuickSort in python with last element as pivot

Question

I can’t seem to get this done correctly. I’ve pasted my code below. Using the print statements, I think what’s happening is that the result of the first pass is what is being returned as the answer, although all the recursive steps show output via print that they’re working as intended, but it seems as though the result isn’t being saved? I was trying to do this in-place, which I tried to do but just modifying array[], but I feel as though I have some misconceptions here. Any help is appreciated.

Codepad: http://codepad.org/jVMbbJTq

Code:

def quicksort(array):
    if len(array) >1:
        print "enter array", array
        pivot = len(array) - 1
        print "pivot", array[pivot]
        x = 0
        while x < pivot:
            if array[x]>array[pivot]:
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
        #        temp = array[x]
         #       array[x] = array[pivot]
         #       array[pivot] = temp
               # array.append(array.pop(x))
                pivot -= 1
            else:
                x += 1
        print "pre recur split array", array
        print "left", array[:pivot]
        print "right", array[pivot+1:]
        quicksort(array[:pivot])
        quicksort(array[pivot+1:])
        print "post recur split array", array
    return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
print "answer", test

Answer 1

I'm not sure if it's the only problem with your code, but one big issue you have is that your recursion won't do anything useful. That is, these two lines do nothing for you:

    quicksort(array[:pivot])
    quicksort(array[pivot+1:])

The reason they do nothing is that the slice you do copies the data from the input list array into a new list. Then the recursive call tries to sort the copied list. The recursive sorting doesn't change the original list at all, so if you ignore their return values, nothing ends up changed in the calling code.

There are a few ways to fix the issue. A simple (but inefficient) fix would be to assign the value returned by each of the recursive calls back into a slice of original list:

    array[:pivot] = quicksort(array[:pivot])
    array[pivot+1:] = quicksort(array[pivot+1:])

If you're going to do something like that though, using temporary lists for the partitioning steps earlier in the code might make everything easier to understand (there's no reason to partition in-place if you're going to copy all the data anyway during the recursion).

Here's a really quick and dirty quicksort that copies things a bunch (and so it is not very efficient):

def quicksort(array):
    if len(array) <= 1:
        return array
    pivot_val = array[-1]
    lower = [x for x in array if x < pivot_val]
    upper = [x for x in array if x > pivot_val]
    pivot_count = array.count(pivot)
    return quicksort(lower) + [pivot_val]*pivot_count + quicksort(upper)

A different, more efficient approach would be to avoid making any copies of the data (which means no slicing). Just sort everything in-place, including the recursive parts. For this to work, you'll need to be able to pass extra arguments in the recursive calls to specify which range of indexes need to be sorted. Fortunately, it's easy to add optional arguments to a function in Python (another option is to have a separate helper function that handles all the recursion).

This involves more changes to your code than the simple fix above, as you can no longer use len(array) as a guide to where the pivot should be found (or to tell when you're done recursing). Here's a quick attempt at it, but I may have an off by 1 error or some other mistakes that you'll need to debug:

def quicksort(array, low=0, high=None):    # add optional arguments
    if high == None:
        high = len(array) - 1              # set high if it got the default
    if high - low > 0:
        pivot = high                       # use high and low to set up pivot and x
        x = low
        while x < pivot:
            if array[x]>array[pivot]:      # this part stays the same
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
                pivot -= 1
            else:
                x += 1
        quicksort(array, low, pivot-1)     # pass on new high and low values
        quicksort(array, pivot+1, high)
    return array                           # you probably don't need this line any more

If you go for this in-place approach, you might want to get rid of the return array part of the function. The standard for Python functions that operate in place is to return None (which is what happens if you don't have any return statement). Many methods that you'll be familiar with work like this. For instance, list.append doesn't return anything, nor does list.sort (the "official" sorting function). Functions in standard library modules, like random.shuffle will also return None when the modify a list that you pass them.

Answer 2

The problem is quicksort(array[:pivot]) and quicksort(array[pivot+1:]) don't modify the array they receive, they return the sorted one. Even if they did though, if you call a function with a sliced list as a parameter and modify that parameter inside the function, the original list is not affected.

A way to fix your algorithm would be like this:

def quicksort(array):
    if len(array) >1:
        print "enter array", array
        pivot = len(array) - 1
        print "pivot", array[pivot]
        x = 0
        while x < pivot:
            if array[x]>array[pivot]:
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
                pivot -= 1
            else:
                x += 1
        print "pre recur split array", array
        print "left", array[:pivot]
        print "right", array[pivot+1:]
        array = quicksort(array[:pivot]) + [array[pivot]] + quicksort(array[pivot+1:])
        print "post recur split array", array
    return array

I'll also include a more "Pythonic" implementation, which uses the filter function to get the lists of elements that are lower and higher than the pivot respectively. At it's core, it's the same algorithm your solution uses; but it's cleaner.

def quick_sort(l):
    if len(l) > 1:
        # Get the last element
        pivot = l[-1]
        # Get a list of all the elements of l lower that the pivot
        lower = list(filter(lambda x: x < pivot, l))
        # Now the higher ones
        higher = list(filter(lambda x: x > pivot, l))
        l = quick_sort(lower) + [pivot] + quick_sort(higher)
    return l