Quicksort - CLRS implementation in python

Question

I am trying to implement quick sort in python. The CLRS algo version.

Here is what i have written. I think it is working fine for the most part except for the middle elements of the list.

Can someone help?

#! /usr/bin/python

#quick sort

def swap(array,i,j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

def partition(array, start,end):
    x = array[end]
    i = start -1
    for j in xrange(start+1, end):
        if (array[j] <= x):
            i = i+1
            swap (array,i,j)
        swap(array,i+1,end)
    return i+1

def quicksort(array,p,r):
    if p<r:
        q = partition(array,p,r)
        quicksort(array,p,q-1)
        quicksort(array,q+1,r)

def main():
    unsortedArray = [2,8,7,1,3,5,6,4,9,0]
    quicksort(unsortedArray,0,len(unsortedArray)-1)
    print unsortedArray


if __name__ == '__main__':
    main()

The output should be [0,1,2,3,4,5,6,7,8,9].Instead it is printing [2, 0, 3, 4, 1, 6, 5, 7, 9, 8].

Answer 1

According to the pseudocode I found on https://users.cs.fiu.edu/~giri/teach/5407/F08/Lec7.pdf, your implementation of partition is wrong, because

swap(array,i+1,end)

should NOT be carried out in every iteration, but instead only once in the function.

I rewrote it like this:

def partition(array, start,end):
    x = array[end]
    i = start -1
    for j in xrange(start, end):
        if (array[j] <= x):
            i = i+1
            swap (array,i,j)
    swap(array,i+1, end)
    return i+1

and it works fine.