various quicksort implementations

quicksort.py

import random
from datetime import datetime
####################
# implementation 1 #
####################
# basic implementation
def quicksort1(l):
    size = len(l)
    # stop condition for reqursive calls
    if size<=1:
        return l
    # buckets for lesser and greater numbers
    lesser = []
    greater = []

    # find pivot element and remove it from the list 
    index = int(size/2)
    pivot = l[index]
    # it is okay to remove some other element that has same name with our element
    l.remove(pivot)
    #separate elements to greater and lesser buckets
    for i in l:
        if i >= pivot:
            greater.append(i)
        else:
            lesser.append(i)
    # call quicksort on lesser and greater buckets and concatenate resulted arrays
    lesser =  quicksort1(lesser)
    lesser.append(pivot)
    return lesser + quicksort1(greater)
    #return quicksort1(lesser)+[pivot]+quicksort1(greater)

####################
# implementation 2 #
####################
# in place sorting implementation
# his is actually slower in python
def quicksort2part(l,start,end,pivot_index):
    #get pivot value
    pivot = l[pivot_index]
    #move pivot to end of list
    l[pivot_index],l[end]=l[end],l[pivot_index]
    #sort elements
    store_index = start
    for i in range(start,end+1):
        if l[i]<=pivot:
            l[i],l[store_index] = l[store_index],l[i]
            store_index+=1
    #return new place of pivot
    return store_index - 1

def quicksort2(array,left,right):    
    if left<right:
        #choose a pivot
        pivot_index = int((right-left)/2)
        #sort array and update pivot index
        pivot_index = quicksort2part(array,left,right,pivot_index)
        # sort lesser and greater elements
        quicksort2(array,left,pivot_index-1)
        quicksort2(array,pivot_index+1,right)


####################
# implementation 3 #
####################
# pythonized version of implementation 1
def quicksort3(l):
    if len(l)<=1:
        return l
    pivot_index = 0
    pivot = l[pivot_index]
    lesser = quicksort3([i for i in l[1:] if i<pivot])
    greater = quicksort3([i for i in l[1:] if i>=pivot])
    return lesser + [pivot] + greater


####################
# implementation 4 #
####################
# one line version of implementation 3
def quicksort4(l):
    return l if len(l)<=1 else quicksort4([x for x in l[1:] if x<l[0]]) + l[:1] + quicksort4([x for x in l[1:] if x>=l[0]]) 

#tests
if __name__ == '__main__':
    SIZE = 10000
    # create test lists
    l = [int(random.random()*SIZE*10)for i in range(SIZE)]
    l1 = l[:]
    l2 = l[:]
    l3 = l[:]
    l4 = l[:]
    l5 = l[:]

    start = datetime.now()
    l2 = sorted(l2)
    end = datetime.now()
    print('native',end-start)

    start = datetime.now()
    l1 = quicksort1(l1)
    end = datetime.now()
    print('implementation-1 ',end-start)

    start = datetime.now()
    l3 = quicksort2(l3,0,len(l3)-1)
    end = datetime.now()
    print('implementation-2 ',end-start)

    start = datetime.now()
    l4 = quicksort3(l4)
    end = datetime.now()
    print('implementation-3 ',end-start)

    start = datetime.now()
    l5 = quicksort4(l5)
    end = datetime.now()
    print('implementation-4 ',end-start)
    
    ytu-huseyin-yilmaz:~ huseyin$ python quicksort.py
# Output
# ######################################################
# ('native', datetime.timedelta(0, 0, 4449))
# ('implementation-1 ', datetime.timedelta(0, 0, 51406))
# ('implementation-2 ', datetime.timedelta(0, 0, 65340))
# ('implementation-3 ', datetime.timedelta(0, 0, 42724))
# ('implementation-4 ', datetime.timedelta(0, 0, 50097))
# ytu-huseyin-yilmaz:~ huseyin$ python --version
# Python 2.7.5
# ytu-huseyin-yilmaz:~ huseyin$