My divide and conquer algorithm works, but my code isn't returning a value

Question

So I'm attempting to learn to code the right way, and I'm going through an Algorithms and Data Structures book. As part of an exercise to teach the reader the value of algorithms (before we even begin learning them), I'm solving a coding exercise problem which will find the kth smallest integer in a list of ints in O(N) time. I'm avoiding searching out the answer because I want to solve it on my own for the brain exercise. Anyway, I've got the code MOSTLY working with an admittedly clumsy divide and conquer algorithm.
I don't want ANY help on the algorithm itself!! I just want to know what I'm doing wrong in the sense that I'm able to print the output, but returning it doesn't work.

alg_list = [7, 10, 18, 3, 8, 11, 9, 15, 0, 14, 12, 16, 6, 5, 2, 13, 17, 4, 1, 19]

def kth_smallest(k, input_list):
  N = len(input_list)
  if N == k:
    input_list.sort()
    M = input_list[-1]
    print M  # used this to get some output to ensure the algorithm works at least
    return M #this is where Im confused.  Why no return?
  else:
    if N == 1:
        M = input_list[0]
        #print '2nd condition'
        return M
    elif N%2 == 0:
        M = input_list[N/2]
        #print '3rd condition'
    else:
        M = input_list[(N - 1)/2]
        #print '4th'
    list_small = [x for x in input_list if x < M]
    list_large = [x for x in input_list if x > M]
    if len(list_small) == k - 1:
        #print '5th'
        return M
    elif len(list_small) > k - 1:
        #print '6th'
        kth_smallest(k, list_small)
    elif (len(list_large) + len(list_small)) == (k - 1):
        #print '7th'
        return M
    elif (len(list_large) + len(list_small)) == k:
        #print '8th'
        new_list = list_large + list_small
        kth_smallest(k, new_list)
    else:
        #print '9th'
        kth_smallest(k, list_large)

kth_smallest(3, alg_list)

Prints 3 here, but if I comment out the print statement, it will not return 3. What am I doing wrong here with returning the value "M"?? Again, I'm sure my crappy attempt at the algorithm is bad, but I'm at the very beginning of the book and this exercise is just to get the reader thinking, so I'm fine with it being bad now. I just want to know what I'm doing wrong with returning a value. I'm assuming its something very obvious that I'm missing.

Thanks!!

There's only a handful of branches in which you're returning anything. Double check your recursive calls and check to see if you should put return in front of any of them. I'm thinking you should. — Makoto
Thanks! this was immensely helpful. It amazes me how stupid my brain can be with subtle details like this! — JPKab
That algorithm is not O(n), by the way... The whole point is to avoid the sort — Niklas B.
Thanks Niklas. You are correct in me dropping the M. I'll have to adjust. Also aware of the need to get rid of the sort. — JPKab

barak manos barak manos · Accepted Answer · 2014-02-05T20:37:04

Inside function kth_smallest, add return to the left of each call to kth_smallest.

Then, outside this function, change:

kth_smallest(3, alg_list)

To:

val = kth_smallest(3, alg_list)
print val

Or simply:

print kth_smallest(3, alg_list)

My divide and conquer algorithm works, but my code isn't returning a value

1 Answers