빠른 정렬 Hoare 배열 파티셔닝

Question

Hoare 파티셔닝 알고리즘이 항상 배열을 두 개의 오른쪽 파트로 분할하는 이유를 알아 내려고합니다. 아래의 코드에서, 나는 Hoare algorithm이 좀 더 명확 나에게 할

int partition(int[] arr, int leftIndex, int rightIndex) { 
    int pivot = arr[(leftIndex + rightIndex)/2]; 

    while (leftIndex <= rightIndex) { 
    while (arr[leftIndex] < pivot) leftIndex++; 
    while (arr[rightIndex] > pivot) rightIndex--; 

    // If all numbers at right places, than leftIndex and rightIndex 
    // could point at same array element index 
    // So it's means partion done. 
    // We should return leftIndex + 1 cause 
    // rightIndex points at the last element of the left sub array 

    if (leftIndex == rightIndex) return leftIndex + 1; 

    if (leftIndex < rightIndex) { 
     swap(arr, leftIndex, rightIndex); 
     leftIndex++; 
     rightIndex--; 
    } 
    } 

    //But here the tricky thing: Why does this "if case" never execute? 
    if (leftIndex - 1 > rightIndex) 
    System.out.println("leftIndex - 1 > rightIndex"); 

    return leftIndex; 
} 

그래서 질문입니다 (자세한 내용은 주석 참조) 확장 : 그것은 가능 기능을 분할하는 배열을 전달하기를, 그래서 라인은 아래 실행됩니다 ? 즉 실행하려면

if (leftIndex - 1 > rightIndex) 
    System.out.println("leftIndex - 1 > rightIndex");? 

Answer 1

, 우리가 leftIndex로 기능을 시작 가정, leftIndex 적어도 rightIndex + 2 할 것이다, 그것은 단지 일어날 수 < = rightIndex :이 두 개의 루프와

:

while (arr[leftIndex] < pivot) leftIndex++; 
while (arr[rightIndex] > pivot) rightIndex--; 

색인은 서로 교차 할 수 없습니다. 색인이 서로 교차 할 수 없습니다. 더 빨리 색인을 생성하지 않으면 피벗의 양쪽에서 중지됩니다.

if (leftIndex == rightIndex) return leftIndex + 1; 

그래서, 남아있는 유일한 방법은 다음과 같습니다 :

if (leftIndex < rightIndex) { 
    swap(arr, leftIndex, rightIndex); 
    leftIndex++; 
    rightIndex--; 
} 

가 될 수있는만큼 가까이있어하더라도 (leftIndex == rightIndex - 1 이러한 경우

그런 다음 우리는 기능을 중단), 실행 후 그들은 leftIndex == rightIndex + 1에있을 것입니다. 그리고 우리는 여전히 2의 차이를 얻지 못했습니다.