I'm working on a quickselect algorithm. I'm not entirely sure my algorithm is working correctly but I don't think that is relevant to the behavior i'm seeing.
I have a recursive algorithm with a conditional check to exit the algorithm with a return printing the final quickselect solution. The conditional is triggered but I kept getting None returned. So I added a print statement right before the return. The print statement prints the value but the return still returns None.
Heres my code. The conditional is on line 11:
#!/usr/bin/env python
from random import randint
def rSelect(arr, k, left=0, right=None):
if right == None:
right = len(arr)
if right == 1:
return arr[k]
else:
j = partition(a,left, right)
if j == k:
print "arr: %s" % arr
print "j: %s" % j
print "arr[j]: %s" % arr[j]
return arr[j]
if j > k:
rSelect(arr, k, left, j)
if j < k:
rSelect(arr, k-j, j+1, right)
def partition(a, l, r):
""" randomized pivot """
p = randint(l,r-1)
a[l], a[p] = a[p], a[l]
i = l + 1
for j in range(l+1, r):
if a[j] < a[l]:
a[j], a[i] = a[i], a[j]
i += 1
a[l], a[i-1] = a[i-1], a[l]
return i-1
a = [ 5,4,3,2,1 ]
print rSelect(a, 1)
