inplace quick sort implementation

Question

I am trying to implement the inplace quick sort as explained in the http://en.wikipedia.org/wiki/Quicksort

Below is the python code, The partition function does not work as expected.

def swap(array, index1, index2):
    tmp = array[index1]
    array[index1] = array[index2]
    array[index2] = tmp

def partition(array, left, right, pivotIndex):
    pivotValue = array[pivotIndex]
    swap(array, pivotIndex, right)
    storeIndex = left
    for i in range(left, right - 1):
        if array[i] < pivotValue:
            swap(array, i, storeIndex)
            storeIndex = storeIndex + 1
            print array, i
    swap(array, storeIndex, right)
    return storeIndex

def quicksort(array, left ,right):
    if right > left:
        print left, right
        pivotIndex = left
        pivotNewIndex = partition(array, left, right, pivotIndex)
        quicksort(array, left, pivotNewIndex - 1)
        quicksort(array, pivotNewIndex + 1, right)

if __name__ == '__main__':
    array = [3,7,8,5,2,1,9,5,4]
    partition(array, 0, len(array) - 1, 3) # 5 is pivot
    print array # expecting all the elements to the left of pivot value(5) will be lesser or equal.

"does not work as expected" -- What is expected? What does it do instead? Try to be specific. Sometimes in figuring these things out, it makes the answer clear to you. — mgilson, Aug 27 '12 at 19:17
You need to explain how you expect it to work and how that's different from what you're actually seeing. — Bill the Lizard, Aug 27 '12 at 19:18
You're using `range` function in a wrong way, fix it (Maxim Skurydin's answer is right). But generally you can write this code more pythonic, Look at these examples of quicksort in python: http://en.literateprograms.org/Quicksort_(Python) — MostafaR, Aug 27 '12 at 19:43
I've got a working Quicksort in Pure Python and Cython available here: http://stromberg.dnsalias.org/~strombrg/sort-comparison/ — dstromberg, Aug 27 '12 at 22:37

Maksim Skurydzin · Accepted Answer · 2012-08-27T19:42:18.003

You need to make at least 2 fixes:

def partition(array, left, right, pivotIndex):
    pivotValue = array[pivotIndex]
    swap(array, pivotIndex, right)
    storeIndex = left
    for i in range(left, right):    # range doesn't include right element already
        if array[i] <= pivotValue:  # need to check for equality (not really necessary for the sorting routine)
            swap(array, i, storeIndex)
            storeIndex = storeIndex + 1
            print array, i
    swap(array, storeIndex, right)
    return storeIndex

range(left, right) returns a list of items like this [left, left + 1, ..., right - 1], so there is no need to do generate a list with range(left, right -1), because thus we shall skip not only the last element of the list (where pivot is), but also the one before last (i.e. right - 2).

If it is expected that after partition the elements on left from pivot should be less than or equal, we should reflect it in the comparison during the array traversal (array[i] <= pivotValue).

That is correct, it shouldn't affect the overall sorting algorithm. However, the OP mentions in the comment that he expects that `all the elements to the left of pivot value(5) will be lesser or equal.` — Maksim Skurydzin, Aug 27 '12 at 19:41

score 0 · Answer 2 · answered Jun 01 '17 at 09:24

is it not better way using less variables and clean approach

#!/usr/bin/python

Array = [1,2,3,4,5,4,3,23,4,5,4,3,2,1,2,3,4,3,4,1,412,2,4]

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

def partition(a, left, right):

    pivotIndex=right
    for i in range(left,right):
        if a[i] > a[pivotIndex]:
            swap(a,i,pivotIndex)


    return pivotIndex

def quicksort(array , left,right):

    if left<right:
        pivotIndex=partition(array,left,right)
        quicksort(array, left, pivotIndex-1)
        quicksort(array, pivotIndex+1, right)

def main():
    quicksort(Array, 0 , len(Array) -1)   
    print (Array )

main()

inplace quick sort implementation

2 Answers2

Linked