첫 번째 인덱스 대신 피벗이있는 퀵 정렬이 잘못 정렬됩니다.

Question

빠른 키. 피벗이 중간 값일 때이 코드가 작동하도록 고심하고 있습니다. 피벗이 가장 왼쪽 값일 때 작동한다는 것을 알고 있습니다. 어떤 도움을 주시겠습니까?

public class Quicksort { 

    public static void main(String[] args) { 
     int[] numbers = { 1, 3, 6, 2, 2, 2, 4, 8, 4 }; 
     System.out.println(Arrays.toString(numbers)); 
     sort(numbers); 
     System.out.println(Arrays.toString(numbers)); 
    } 

    public static void sort(int[] number) { 
     quicksort(number, 0, number.length - 1); 
    } 

    public static void quicksort(int[] array, int left, int right) { 
     int lowest = left, highest = right; 

     if (right - left >= 1) { 
      int pivot = array[(left + right)/2]; 
      // works when pivot = array[left]; 
      while (lowest < highest) { 
       while (array[lowest] <= pivot && lowest <= right && highest > lowest) { 
        lowest++; 
       } 
       while (array[highest] > pivot && highest >= left && highest >= lowest) { 
        highest--; 
       } 
       if (highest > lowest) { 
        swap(array, lowest, highest); 
       } 
      } 
      swap(array, left, highest); // problem area? 
      quicksort(array, left, highest - 1); 
      quicksort(array, highest + 1, right); 
     } else { 
      return; 
     } 
    } 

    public static void swap(int[] array, int index, int index1) { 
     int temp = array[index]; 
     array[index] = array[index1]; 
     array[index1] = temp; 
    } 

} 

이의 출력은 피터 Lawrey에 의해 제안에 따라

[1, 3, 6, 2, 2, 2, 4, 8, 4] //unsorted 
    [2, 2, 2, 1, 3, 4, 4, 6, 8] //wrongly "sorted" 

Answer 1

, 내가 먼저 프로그램이 두 개의 숫자를 올바르게 정렬하는 것을 관찰했다. 그런 다음 세 가지로 시도 :

int[] numbers = { 1, 3, 6 }; 

당신의 while 루프 후에는이 경우 귀하의 코멘트에

• left = 0
• lowest = 2
• highest = 1

이 problem area? 올바른 sonce 것 당신은 1과 3 번 번호를 교환하고, 따라서 그것들을 질서 정연하게 만든다. 일반적으로

, 루프 후에는 <= pivot 및 array[highest + 1..right]하는 > pivot입니다 array[left..lowest - 1]이 있다는 것을 알고,하지만 난 당신이 array[highest] 하나의 일부 또는 기타에 속하는지 여부를 확신 할 수 있다고 생각하지 않습니다 lowest == highest 경우, 그래서 당신은 여부를 알 수없는 그것을 왼쪽 부분으로 바꾸려면.

그런데 int pivot = array[left];과 동일한 문제가 있습니다. int[] numbers = { 3, 1, 6 };을 시도하면 결과는 [3, 1, 6]입니다.