MattTheSnake MattTheSnake - 2 months ago 12
Python Question

How do I improve my quick sort pivot selection in python?

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

You could choose the pivot in this way:

alen = len(array)
pivots = [[array[0],0], [array[alen//2],alen//2], [array[alen-1],alen-1]]]
pivots.sort(key=lambda tup: tup[0]) #it orders for the first element of the tupla
pivot = pivots[1][1]

Example:

enter image description here