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]

• eightnoteight: yes, it does a lot of swaps, especially when encountered a max element.

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.

• eightnoteight: 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?
• vnp: For purely random data it makes no difference.