Hoare 파티셔닝이 무한 루프에 빠지다

Question

나는 배열을 입력으로 사용하는 Hoare 파티셔닝 함수를 작성하려고합니다. 첫 번째 요소를 피벗으로 파티션합니다 (나는 좋은 생각이 아니라는 것을 알고 있습니다. 랜덤 피벗을 사용해야합니다. median-of-medians 접근 방식처럼). 배열 [14,6,8,1,4,9,2,1,7,10,5]처럼 첫 번째 요소가 가장 높을 때이 함수가 무한 루프에 빠지는 문제가 있습니다. 나는 외부 while의 첫 번째 반복 이후에 i과 j이 모두 같기 때문에 오류를 볼 수 있으며 따라서 루프는 영원히 계속됩니다. 원하는 효과를 얻기 위해 어느 부분을 고쳐야합니까? 여기에 코드입니다 :

def hoare(arr): 
    pivot = arr[0] 
    i,j = 1,len(arr)-1 
    while i <= j: 
     while i < j and arr[i] < pivot: 
      i += 1 
     while j >= i and arr[j] >= pivot: 
      j -= 1 
     if i < j: 
      arr[i],arr[j] = arr[j],arr[i] 
    if j != 0: 
     arr[0],arr[j] = arr[j],arr[0] 
     return j 

Answer 1

나는 문제가 당신이 할 - 동안 전환했다고 믿는다 (또는 반복-때까지, 호어의 측면에서) 루프를 while 루프로는, 그래서 첫 번째 J를하지 결코 - = 1.

파이썬 간단한 변환이 같은 루프 동안 두 내측을 변경하는 것 :

while True: 
    i += 1 
    if not (i < j and arr[i] < pivot): break 
while True: 
    j -= 1 
    if not (j >= i and arr[j] >= pivot): break 

(I는 if i < j: 것으로하고 여기 가정하고있어 반복하면서 제 2 외측으로하고, 다른 모든 초기 들여 쓰기는 정확합니다.)

나는 이것을 완전히 추론하지 않았거나 다양한 테스트를 실행했지만 번역에이 오류 하나 이상이있을 수 있습니다. 또한 외부 루프를 do-while으로 변환해야 할 수도 있습니다 (실제로 Hoare는 끝에 검사를 명시 적으로 while TRUE로 지정합니다). 그러나 확실하지 않습니다. 어쨌든 샘플 입력의 경우 수정 된 버전은 9이고 arr은 [10, 6, 8, 1, 4, 9, 2, 1, 7, 14, 5]이며 올바르지 않지만 무한 루프 문제가 해결됩니다.

다음 문제는 off-by-one 오류입니다. 내부 루프에서 += 1과 -= 1을 먼저 수행하려면 0, len(arr)-1 (또는 이전처럼 1, len(arr)-1)이 아닌 -1, len(arr)부터 시작해야합니다.

다른 문제가있을 수 있습니다. 그러나 나는 가능한 모든 실수를 찾아 설명하는 코드를 파헤 치고 싶지 않습니다. 필요하다면 소스가 무엇인지 알려주고 소스에서 만든 각각의 변형을 설명하면 잘못 된 부분을 설명하는 것이 훨씬 쉬울 것입니다. 그렇지 않다면 Hoare의 알고리즘을 Python으로 직접 변환 한 다음 훨씬 더 간단하게 이해할 수 있습니다. 여기

은 (두 공간으로 모든 탭을 대체) 온라인 내가 찾은 호어의 의사 코드의 복사본입니다 :

여기

Hoare-Partition (A, p, r) 
    x ← A[p] 
    i ← p − 1 
    j ← r + 1 
    while TRUE 
    repeat j ← j − 1 
     until A[j] ≤ x 
    repeat i ← i + 1 
     until A[i] ≥ x 
    if i < j 
     exchange A[i] ↔ A[j] 
    else 
     return j 

파이썬에 사소한 번역입니다; 유일한 변경 사항은 사소한 구문 ("교환"철자 포함)과 각 반복/한 번을 참/거짓으로 전환하는 것입니다. 당신과 같은 서명을 가진 함수의

def hoare(a, p, r): 
    x = a[p] 
    i, j = p-1, r+1 
    while True: 
    while True: 
     j -= 1 
     if a[j] <= x: 
     break 
    while True: 
     i += 1 
     if a[i] >= x: 
     break 
    if i < j: 
     a[i], a[j] = a[j], a[i] 
    else: 
     return j 

: 내가 J <경우`후 라인이 있기 때문에

def hoare0(arr): 
    return hoare(arr, 0, len(arr)-1)