Will Will - 5 months ago 26
Python Question

Bug with in-place quick selection (aka linear time selection) in Python

I am following the Stanford course "Algorithms: Design and Analysis, Part 1", while trying implement an in place randomized selection algorithm in Python (i.e. selection based on quick sort), I believe my partition function is correct, but I just cannot figure out why the selection part keeps failing, any suggestion is greatly appreciated. My code is as follows:

import random
def random_selection(nums, start, end, i):
if end == start:
return nums[start]
elif start < end:
pivot = partition(nums, start, end)
if pivot == i:
return nums[pivot]
elif pivot < i:
return random_selection(nums, pivot + 1, end, i - pivot)
elif pivot > i:
return random_selection(nums, start, pivot - 1, i)
else:
return False


def partition(nums, start, end):
pivot_value = nums[start]
left = start + 1
right = end
done = False
while not done:
while left <= right and nums[left] < pivot_value:
left += 1

while left <= right and nums[right] > pivot_value:
right -= 1

if left > right:
done = True
else:
nums[left], nums[right] = nums[right], nums[left]
nums[start], nums[right] = nums[right], nums[start]
return right

test = range(10)
for i in range(10):
random.shuffle(test)
print random_selection(test, 0, len(test)-1, i)


Below are the results I am receiving with the test case:


0

1

None

3

4

None

5

4

8

None

Answer

The problem is you need to decide whether your indices are based on 0, or based on start.

Most of the code uses indices based on 0, except the recursive call to random_selection:

return random_selection(nums, pivot + 1, end, i - pivot)

which adjusts the i index to i - start (i.e. assuming the indices are based on start).

Changing this to:

return random_selection(nums, pivot + 1, end, i)

should give the expected results.