Quicksort

quicksort.py

'''
Gabriel C. 2015
 
Quicksort with 3 different pivot-choosing methods
'''

def quicksort(array, method):
    return quicksort_aux(array, 0, len(array) - 1, method)

def swap(array, a, b):
    elem = array[a]
    array[a] = array[b]
    array[b] = elem

#First
def choose_pivot1(array, left, right):
    return array[left]

#Last
def choose_pivot2(array, left, right):
    swap(array, left, right)
    
    return array[left]

#Median
def choose_pivot3(array, left, right):
    middle = (right - left) / 2 + left
    
    if right - left % 2 == 0:
        middle += 1

    p = median(array, left, middle, right)
    
    swap(array, left, p)

    return array[left]

def median(array, left, middle, right):
    a = array[left]
    b = array[middle]
    c = array[right]
    
    if (a <= b <= c) or (c <= b <= a):
        return middle

    if (b <= a <= c) or (c <= a <= b):
        return left

    return right

def quicksort_aux(array, left, right, method):
    if right <= left:
        return 0

    if method == 1:
        p = choose_pivot1(array, left, right)
    elif method == 2:
        p = choose_pivot2(array, left, right)
    else:
        p = choose_pivot3(array, left, right)
        
    i = left + 1
    
    for j in xrange(i, right + 1):
        if array[j] < p:
            swap(array, j, i)
            i = i + 1

    swap(array, left, i - 1) 

    return right - left + quicksort_aux(array, left, i - 2, method) + quicksort_aux(array, i, right, method)