파이썬 Quickselect 여기 피벗

Question

를 반환/인쇄되지 내가 그것으로 데 문제가이 오류없이 또는 아무것도 실행한다는 것입니다 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) 

의 코드이지만, 그 자체를 완료 할 때 나는 그것을 기대하고있다 파이썬 쉘 (이 특정 경우에는 목록의 중앙값)에 뭔가를 출력하지만, 나는 아무것도 얻지 못합니다. 내가 여기서 뭔가 잘못하고있는거야? I는 LST 및 k에 대한 입력하고 어떤로서는

....

• LST = [70, 120, 170, 200]
• K = LEN (LST) // 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)