In-Place Quicksort in Python

Question

Code is below. I'd like to know if this is a solid/efficient implementation of the in-place quicksort algorithm and if my Python style is good (I know there are no comments for now). Code is also on Github here if you'd like: https://github.com/michaelrbock/data-structs-and-algos/blob/master/Sorts/quicksort.py Thanks!

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    lst, store_index = partition(lst)
    return quicksort(lst[:store_index-1]) + [lst[store_index-1]] + quicksort(lst[store_index:])

def partition(lst):
    if len(lst) % 2 == 0:
        middle = (len(lst) / 2) - 1
    else:
        middle = len(lst) / 2

    pivot_choice = get_median( [lst[0], lst[middle], lst[len(lst)-1]] )

    if pivot_choice == lst[0]:
        PIVOT_INDEX = 0
    elif pivot_choice == lst[middle]:
        PIVOT_INDEX = middle
    elif pivot_choice == lst[len(lst)-1]:
        PIVOT_INDEX = len(lst) - 1

    pivot = lst[PIVOT_INDEX]
    lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
    i = 1
    for j in range(1, len(lst)):
        if lst[j] < pivot:
            lst[j], lst[i] = lst[i], lst[j]
            i += 1
    lst[0], lst[i-1] = lst[i-1], lst[0]
    return lst, i

def get_median(nums):
    values = sorted(nums)
    if len(values) % 2 == 1:
        return values[(len(values)+1)/2-1]
    else:
        lower = values[len(values)/2-1]
        upper = values[len(values)/2]
    return (lower+upper)/2

Answer 1

Personally I like the style (especially the nice clear function and variable names). As its quicksort most of the code is straightforward enough that comments would probably only add meaning when it comes to the swapping. You should probably try and use four spaces, rather than tabs, for indenting the code (it's just common practice). The only minor stylistic change I would personally make is to uncapitalise PIVOT_INDEX. I know technically it is constant (in that it doesn't change value after it's assigned), but I just prefer to have one clear assignment for any constant values. However, I'm sure other people would disagree.

As for efficiency, you're always going to be bounded by the algorithm itsef, but there are a couple changes you could make. You calculate len(lst) multiple times in partition. Rather than doing that, you could just assign it like list_length = len(lst) once at the start of the partition function. Not a big deal I know. The only other meaningful change I can think of is in your get_median function. As you know that it's always called with three values you could change it to:

def get_median(nums):
    values = sorted(nums)
    return values[1]

If you really want to be fancy you can replace the get_median and the whole if-then-else construct that determines the PIVOT_INDEX with something like:

PIVOT_INDEX = sorted(zip([lst[0], lst[middle], lst[list_length - 1]], [0, middle, list_length]))[1][1]

which will give you the index (0, middle or list_length) of the median value in the same way.

Answer 2

Your style is good.

I had a little improvement for efficiency. Instead of using the condition i % 2 == 0 for checking i as an even number you can instead use i % 2 as a condition for checking i as an odd number. It reduces the number of comparisons and doesn't effect the functionality at all. It might not have the best readability but it improves time-efficiency. A simple comment can offset the readability lost.

Also this seems like Python 2 so instead of using range which returns a list you should use xrange which returns a generator when you are looping. It costs a little time-performance but is usually compensated by the huge improvement in memory-performance.

Also in the median function you can probably eliminate the lower and upper variable by using something like

return (
    values[len(values)/2-1] +
    values[len(values)/2]
    )/2

Hope this helped.