Quicksort – Python implementation (pivot = the first element of the list)

import random
import time
def swap(array,a,b):
    array[a],array[b] = array[b],array[a]
def partition(array,start,end):
    left = start + 1
    pivot = array[start]
    for right in range(start+1,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 = [random.randint(0,1000) for r in xrange(10000)]
    start = time.time()
    quickSort(array)
    end = time.time()
    print end – start
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: