6
\$\begingroup\$

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))
\$\endgroup\$
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ yes, it does a lot of swaps, especially when encountered a max element. \$\endgroup\$ – eightnoteight Sep 25 '14 at 12:11
3
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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