Search code examples
pythonmedianquickselect

Python Quickselect not printing/returning pivot


Here is the code for quickselect

def quickSelect(lst, k):
if len(lst) != 0:
    pivot = lst[(len(lst)) // 2]
    smallerList = []
    for i in lst:
        if i < pivot:
            smallerList.append(i)
    largerList = []
    for i in lst:
        if i > pivot:
            largerList.append(i)
    count = len(lst) - len(smallerList) - len(largerList)
    m = len(smallerList)
    if k >= m and k < m + count:
        return pivot
        print(pivot)
    elif m > k:
        return quickSelect(smallerList, k)
    else:
        return quickSelect(largerList, k-m-count)

the issue I am having with it is that it runs with no errors or anything, but when it completes itself I am expecting it to output something to the python shell (in this specific case a median of a list), but I get nothing back. Am I doing something wrong here?

As for what I am inputting for lst and k....

  • lst = [70, 120, 170, 200]
  • k = len(lst) // 2

I have tried it with a few different k values as well but to no avail


Solution

  • def quickSelect(lst, k):
        if len(lst) != 0:
            pivot = lst[(len(lst)) // 2]
            smallerList = []
            for i in lst:
                if i < pivot:
                    smallerList.append(i)
            largerList = []
            for i in lst:
                if i > pivot:
                    largerList.append(i)
            count = len(lst) - len(smallerList) - len(largerList)
            m = len(smallerList)
            if k >= m and k < m + count:
                return pivot
                print(pivot)
            elif m > k:
                return quickSelect(smallerList, k)
            else:
                return quickSelect(largerList, k-m-count)
    
    lst = [70, 120, 170, 200]
    k = len(lst) // 2
    
    print(quickSelect(lst, k))
    

    produces

    >>> 170
    

    The only thing I corrected was the indenting.