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

def quicksort(array, lo, hi):
    if hi - lo < 2:
    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))

2 Answers 2


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]
  • \$\begingroup\$ yes, it does a lot of swaps, especially when encountered a max element. \$\endgroup\$ 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.

  • \$\begingroup\$ 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? \$\endgroup\$ Commented Sep 25, 2014 at 12:15
  • \$\begingroup\$ For purely random data it makes no difference. \$\endgroup\$
    – vnp
    Commented Sep 25, 2014 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.