둘 이상의 값이 피벗과 같을 때 호아 분할이 작동하지 않습니다.

Question

호 전세 분할 함수를 잘 이해하기 위해 함수를 작성하려고합니다. 나는 그것의 정의와 의사 코드를 잘 따라 갔다고 생각했지만 많은 경우에 예상대로 작동하는 것처럼 보이지만 피벗과 동일한 값을 가진 목록이 전달되면 무너져 내리고 무한 루프가됩니다. 실수는 어디에서 발생합니까? 버그를 수정하려면 어떻게 수정해야합니까?

def partition(lst, left_index, right_index): 
    pivot = lst[right_index] 


    while True: 
     #Increment left index until value at that index is greater or equal to pivot 
     while True: 
      if lst[left_index] >= pivot: break 
      left_index += 1 

     #Increment right index until value at that index is less or equal to pivot 
     while True: 
      if lst[right_index] <= pivot: break 
      right_index -= 1 

     if left_index < right_index: 
      lst[left_index], lst[right_index] = lst[right_index], lst[left_index] 
     else: 
      return right_index 

return partition(0, end) 

Answer 1

당신은 lst[left_index] >= pivot 및 lst[right_index] <= pivot 모두에서 피벗 값과 동일한 지 어떤지를 테스트하고 있습니다. 이렇게하면 두 인덱스가 피벗 값 요소 위로 건너 뛰는 것을 효과적으로 방지 할 수 있습니다. 따라서 두 개 이상의 피벗 값 요소가 목록의 가운데로 밀리면 left_index 및 right_index은 극복 할 수없는 장벽으로 분리됩니다. 해당 행의 등호를 삭제하면 중단되지 않는 문제는 해결됩니다.

그러나이 변경의 결과로 left_index을 이동하는 루프는 right_index 위의 한 위치만큼 밀어 넣을 수 있으며 right_index이 초기 위치에있을 때 범위를 벗어날 수도 있습니다. 마찬가지로, right_index을 이동하는 루프는 left_index 아래의 한 위치만큼 밀어 넣을 수 있으며 left_index이 초기 위치에있을 때 범위를 벗어납니다. 이러한 일이 발생하지 않도록하려면 해당 루프의 while True:을 while left_index < right_index:으로 변경해야합니다.

left_index 또는 right_index에 대한 일치 확인을 제거하는지 여부에 따라 파티션이 약간 다를 수 있습니다. 피벗 요소가 목록의 가장 작은 값 또는 가장 큰 값으로 밝혀지면 경계의 경우에 중요합니다. 처음에는 이 입력 범위에 대한 내부 위치를 나타내고 left_index이 경계 위치를 가리키는 것을 고려하면 left_index은 피벗 값을 건너 뛸 수 있어야하며 right_index은 피벗 값에서 중지하도록 지시해야합니다 (반대 논리는 알고리즘이 끝날 때까지 left_index을 초기 위치에 유지하면서 right_index을 left_index까지 끝까지 밀어 넣을 수 있으며 분할을 전혀 만들지 않을 수 있습니다.

따라서 수정 된 코드는이 될 것입니다 : 더 이상은 여전히 ​​제대로 목록을 분할하지 않는 무한 루프로 전환 등호를 제거한 후 ... 그것도 보인다하더라도

def partition(lst, left_index, right_index): 
    pivot = lst[right_index] 

    while True: 
     while left_index < right_index and lst[left_index] <= pivot: 
      left_index += 1 

     while left_index < right_index and lst[right_index] > pivot: 
      right_index -= 1 

     if left_index < right_index: 
      lst[left_index], lst[right_index] = lst[right_index], lst[left_index] 
     else: 
      return right_index