Quick-sort “median-of-three” – Python implementation

def swap(array,a,b):
    array[a],array[b] = array[b],array[a]
def partition(array,start,end):
    median = (end – 1 – start) / 2
    median = median + start
    left = start + 1
    if (array[median] – array[end-1])*(array[start]-array[median]) >= 0:
        swap(array,start,median)
    elif (array[end – 1] – array[median]) * (array[start] – array[end – 1]) >=0:
         swap(array,start,end – 1)
    pivot = array[start]
    for right in range(start,end):
        if pivot > array[right]:
            swap(array,left,right)
            left = left + 1
    swap(array,start,left-1)
    return left-1
def quickSortHelper(array,start,end):
    if start < end:
        splitPoint = partition(array,start,end)
        quickSortHelper(array,start,splitPoint)
        quickSortHelper(array,splitPoint+1,end)
def quickSort(array):
    quickSortHelper(array,0,len(array))
if __name__ == “__main__”:
    array = list(xrange(10))
    array.reverse()
    quickSort(array)
    print array

 

For finding “median-of-three” visit the following link:
Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: