선택 알고리즘을 사용하여 정렬되지 않은 목록의 중간 값 얻기

Question

정수 목록이 있습니다.이 정렬되지 않은 목록의 중앙값을 찾기 위해 선택 항목을 사용하고 싶습니다. 이것은 지금까지 가지고있는 것이지만, 테스트 목록 [140, 240, 180, 400, 340]에 대해서는 결과물을 얻지 못하고 있습니다. 누군가가 중간 값을 얻기 위해해야 ​​할 일을 설명 할 수 있습니까?

내 코드

def fastSelect(aList, k): 

    count = 0 
    pivot = 0 
    smallerList = [] 
    largeList = [] 
    while aList != []: 
     pivot == len(aList)//2 
     for i in range(0,pivot): 
      smallerList.append(aList[i]) 
     for j in range(pivot + 1,len(aList)): 
      largeList.append(aList[j]) 
     for g in range(0,len(aList)): 
      if aList[g] == pivot: 
       count += 1 
     m = len(smallerList) 
     if k >= m and k < m + count: 
      return pivot 
     if m > k: 
      aList = smallerList 
     else: 
      k = k - m - count 
      aList = largeList 

Answer 1

당신은 실제로 당신의 pivot 값과 비교 아닙니다. 또한 pivot 초기화를 지정하는 경우 = 대신 ==을 사용하는 버그가 있습니다. pivot가 중간이되는 이유

def fastSelect(aList, k): 
    while aList: 
     smallerList = [] 
     largeList = [] 
     count = 0 
     pivot = aList[len(aList) // 2] 
     for i in aList: 
      if i < pivot: 
       smallerList.append(i) 
      elif i > pivot: 
       largeList.append(i) 
      else: 
       count += 1 
     m = len(smallerList) 
     if k >= m and k < m + count: 
      return pivot 
     if m > k: 
      aList = smallerList 
     else: 
      k = k - m - count 
      aList = largeList 

이해하려면 중간의 정의가 무엇인지에 대해 생각해야합니다. 중앙값은 목록의 값으로 다른 값의 절반 이하이며 다른 값의 절반 이상입니다.

루프를 처음 사용할 때 중간 값은 pivot으로 선택됩니다. 그런 다음 목록을 두 개의 목록으로 분할합니다. 하나는 pivot보다 작은 값을 포함하고 다른 하나는 pivot보다 큰 값을 포함합니다. 유사하게 pivot과 동일한 값의 count이 유지됩니다. 다음으로 각 목록에있는 값의 수를 확인합니다. 두 목록이 같은 크기이거나 count의 차이가있는 경우 정의에 따라 중간 값을 찾았으므로 pivot을 반환합니다.

이제 우리는 루프 전체에서이 불변성을 유지해야합니다. 각각의 경우를 살펴 보겠습니다. smallerList의 크기 (m으로 표시)가 k보다 큰 경우 중간 값은 smallerList 안에 있어야하며 kth 요소는 smallerList 안에 있습니다. k이 m보다 큰 경우, 중간은 largeList 내부에 없어야합니다,하지만 우리는 이미 pivot보다 작거나 같은 m 및 count 요소를 발견했기 때문에 우리는 더 이상 largeList 내부 kth 요소가 필요합니다, 그래서 우리는 k에서 사람들을 빼기 루프를 계속하기 전에.

마지막으로 실제로 임의의 피벗을 사용하여이 코드를 향상시킬 수 있습니다. Quickselect algorithm에있는 Wikipedia의 기사를 보면 무작위 피벗이 거의 일정한 선형 시간 복잡성을 보장하는 반면, 선택한 중간 위치 피봇은 예측 가능한 최악 사례 분석을 보게됩니다.