Python Быстрый выбор не печатает/возвращения пивот

Question

Вот код Быстрый выбор

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) 

вопрос я имею с ним в том, что он работает без ошибок или что-нибудь, но когда он завершает себя я жду его вывести что-то в оболочку python (в этом конкретном случае медиана списка), но я ничего не получил. Я здесь что-то не так?

Что касается того, что я для ввода LST и к ....

• LST = [70, 120, 170, 200]
• к = Len (ЛСТ) // 2

Я попробовал его с несколькими различными значениями K, а также, но безрезультатно

Answer 1

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)) 

производит

>>> 170 

Единственное, что я исправил, это отступы.

Answer 2

Вы можете оптимизировать этот алгоритм, используя понимание списка. Кроме того, я не думаю, что вам нужно подсчитать ...

def quickSelect(seq, k): 
    # this part is the same as quick sort 
    len_seq = len(seq) 
    if len_seq < 2: return seq 

    ipivot = len_seq // 2 
    pivot = seq[ipivot] 

    smallerList = [x for i,x in enumerate(seq) if x <= pivot and i != ipivot] 
    largerList = [x for i,x in enumerate(seq) if x > pivot and i != ipivot] 

    # here starts the different part 
    m = len(smallerList) 
    if k == m: 
     return pivot 
    elif k < m: 
     return quickSelect(smallerList, k) 
    else: 
     return quickSelect(largerList, k-m-1) 




if __name__ == '__main__': 
    # Checking the Answer 
    seq = [10, 60, 100, 50, 60, 75, 31, 50, 30, 20, 120, 170, 200] 

    # we want the middle element 
    k = len(seq) // 2 

    # Note that this only work for odd arrays, since median in 
    # even arrays is the mean of the two middle elements 
    print(quickSelect(seq, k)) 
    import numpy 
    print numpy.median(seq)