quicksort.py

import random


def partition(lst, left, right, pivotIndex):
    # print pivotIndex
    pivotValue = lst[pivotIndex]

    lst[pivotIndex], lst[right] = lst[right], lst[pivotIndex]

    storeIndex = left

    for i in range(left, right):
        if lst[i] < pivotValue:
            lst[storeIndex], lst[i] = lst[i], lst[storeIndex]

            storeIndex += 1

    lst[right], lst[storeIndex] = lst[storeIndex], lst[right]

    return storeIndex


def median3(lst, left, right):
    # print left, right
    center = (left + right) / 2

    # print "center", center
    if lst[center] < lst[left]:
        lst[center], lst[left] = lst[left], lst[center]
        #print "a"
    if lst[right] < lst[left]:
        lst[left], lst[right] = lst[right], lst[left]
        #print "b"
    if lst[right] < lst[center]:
        lst[center], lst[right] = lst[right], lst[center]
        #print "c"

    lst[center], lst[right - 1] = lst[right - 1], lst[center]

    #print "right",lst[right]

    return lst[right - 1]


def select(lst, left, right, k):

    if left + 10 <= right:

            pivotIndex = median3(lst, left, right)
            pivotIndex = partition(lst, left, right, pivotIndex)

            if k == pivotIndex:
                return lst[pivotIndex]
            elif k < pivotIndex:
                return select(lst, left, pivotIndex-1, k)
            else:
                return select(lst, pivotIndex+1, right, k)
    else:
        insertionSort(lst, left, right)

    return lst[k]

def insertionSort(lst, left, right):
    for i in range(left, right):

        j = i
        while j > 0 and lst[j - 1] > lst[j]:
            lst[j], lst[j - 1] = lst[j - 1], lst[j]
            j -= 1



def quickSelect(lst, k):
    return select(lst, 0, len(lst) - 1, k)




print [quickSelect(a, i) for i in range(0, 9)]