Will - 1 year ago 53

Python Question

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.

Source (Stackoverflow)