MattTheSnake - 1 year ago 51

Python Question

I was originally using only a single random pivot given by

`pivots = random.randrange(l,r)`

Here l and r will be integers that define my range

I wanted to improve the run time by greatly increasing the likely hood that my pivot would be a good pivot by selecting the median of three random pivots. Below is the code I used and it caused my run time to increase by 20%-30%.

`rr = random.randrange`

pivots = [ rr(l,r) for i in range(3) ]

pivots.sort()

How do I implement the above to be much faster?

Edit: Entire code added below

`import random`

def quicksort(array, l=0, r=-1):

# array is list to sort, array is going to be passed by reference, this is new to me, try not to suck

# l is the left bound of the array to be acte on

# r is the right bound of the array to act on

if r == -1:

r = len(array)

# base case

if r-l <= 1:

return

# pick the median of 3 possible pivots

#pivots = [ random.randrange(l,r) for i in range(3) ]

rr = random.randrange

pivots = [ rr(l,r) for i in range(3) ]

pivots.sort()

i = l+1 # Barrier between below and above piviot, first higher element

array[l], array[pivots[1]] = array[pivots[1]], array[l]

for j in range(l+1,r):

if array[j] < array[l]:

array[i], array[j] = array[j], array[i]

i = i+1

array[l], array[i-1] = array[i-1], array[l]

quicksort(array, l, i-1)

quicksort(array, i, r)

return array

Edit 2:

This is the corrected code due. There was an error in the algorithm for picking the 3 pivots

`import random`

def quicksort(array, l=0, r=-1):

# array is list to sort, array is going to be passed by reference, this is new to me, try not to suck

# l is the left bound of the array to be acte on

# r is the right bound of the array to act on

if r == -1:

r = len(array)

# base case

if r-l <= 1:

return

# pick the median of 3 possible pivots

mid = int((l+r)*0.5)

pivot = 0

#pivots = [ l, mid, r-1]

if array[l] > array[mid]:

if array[r-1]> array[l]:

pivot = l

elif array[mid] > array[r-1]:

pivot = mid

else:

if array[r-1] > array[mid]:

pivot = mid

else:

pivot = r-1

i = l+1 # Barrier between below and above piviot, first higher element

array[l], array[pivot] = array[pivot], array[l]

for j in range(l+1,r):

if array[j] < array[l]:

array[i], array[j] = array[j], array[i]

i = i+1

array[l], array[i-1] = array[i-1], array[l]

quicksort(array, l, i-1)

quicksort(array, i, r)

return array

Answer Source