Pythonic quicksort algorithm

Question 1

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

Question 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# egpivot = 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 acrossthis 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]

Question 3

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

Question 4

Looks good in general. Few comments.

Missingimport 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 ispartition. It is worthy to be factored out in a function of its own.

Question 5

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?

Question 6

Forpurely random data it makes no difference.

cheezsteak 2,4211 gold badge17 silver badges33 bronze badges · Accepted Answer · 2017-04-13 12:48:30Z

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# egpivot = 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 acrossthis 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.

Movatterモバイル変換

Stack Exchange Network

Pythonic quicksort algorithm

2 Answers2

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS