# Pythonic quicksort algorithm

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))


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]

• yes, it does a lot of swaps, especially when encountered a max element. Commented Sep 25, 2014 at 12:11

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.

• No Raw Loops mantra +1.... and about the second comment, if it is random data, does it make any difference if i took 3 random pivots and finalized the median of pivots as final pivot? Commented Sep 25, 2014 at 12:15
• For purely random data it makes no difference.
– vnp
Commented Sep 25, 2014 at 16:44