Pythonic quicksort algorithm

Question

Is my implementation of quicksort efficient, in-place, pythonic ?

def quicksort(array, lo, hi):
    if hi - lo < 2:
        return
    key = random.randrange(lo, hi)
    array[key], array[lo] = array[lo], array[key]
    y = 1 + lo
    for x in xrange(lo + 1, hi):
        if array[x] <= array[lo]:
            array[x], array[y] = array[y], array[x]
            y += 1
    array[lo], array[y - 1] = array[y - 1], array[lo]
    quicksort(array, lo, y - 1)
    quicksort(array, y, hi)


a = map(int, raw_input().split())
quicksort(a, 0, len(a))

Answer 1

Consider your partition method

for x in xrange(lo + 1, hi):
    if array[x] <= array[lo]:
        array[x], array[y] = array[y], array[x]
        y += 1

Abstracted out it looks something like this.

def partition(array, lo, hi, pivot):
    y = lo
    for x in xrange(lo, hi):
        if array[x] <= pivot:
            array[x], array[y] = array[y], array[x]
            y += 1
    return y

# eg
pivot = partition(array, lo + 1, hi, array[lo])
array[lo], array[pivot] = array[pivot], array[lo]

That struck me as an odd partition method. It's not the one I learned yet it is simpler and seems to work. When searching for an example I came across this question on cs.exchange. You should read the very detailed answer and consider using the Hoare partition as it always slightly more efficient.

Also you should consider implementing a separate swap method. The idiom you use is perfectly fine it just gets verbose and you use it often enough

def swap_indexes(array, a, b):
    array[a], array[b] = array[b], array[a]

Answer 2

Looks good in general. Few comments.

• Missing import random.

• Random pivot selection is just one of many possible strategies. It may or may not be a good strategy depending on the nature of data. Only the client knows what a suitable strategy will be; let him chose.

• No Raw Loops mantra: Every loop possible represents an algorithm, often very important itself. In this case the algorithm is partition. It is worthy to be factored out in a function of its own.