quicksort.py

# Inplace quicksort in python
from functools import partial
import operator
import random
import time


def partition(list_, l, r, p):
    pVal = list_[p]
    list_[p], list_[r] = list_[r], list_[p]
    store_index = l
    for i in range(l, r):
        if list_[i] < pVal:
            list_[i], list_[store_index] = list_[store_index], list_[i]
            store_index += 1
    list_[r], list_[store_index] = list_[store_index], list_[r]
    return store_index


def _quicksort(list_, l, r):
    if l < r:
        p = l + 1
        p = partition(list_, l, r, p)
        _quicksort(list_, l, p - 1)
        _quicksort(list_, p + 1, r)


def inplace_quicksort(list_):
    _quicksort(list_, 0, len(list_) - 1)


def hoggy_quicksort(list_):
    if len(list_) <= 1:
        return list_
    i = len(list_) / 2
    partition = list_.pop(i)
    lesser = filter(
        partial(operator.gt, partition), list_)  # partition > item
    greater = filter(
        partial(operator.le, partition), list_)  # partition <= item
    return hoggy_quicksort(lesser) + [partition] + hoggy_quicksort(greater)


l = range(1, 10)
before = list(l)
random.shuffle(l)
start = time.time()
l = hoggy_quicksort(l)
print l
# # inplace_quicksort(l)
# duration = time.time() - start
# print duration, 'seconds'
# assert l == before, "The list was not sorted"