Quicksort가 예상대로 작동하지 않습니다.

Java에서 quicksort 용 CLRS 의사 코드를 구현하려고하는데 배열을 올바르게 정렬 할 수 없습니다. 내가 쓴 코드는 다음과 같습니다 내가 그 코드를 가지고Quicksort가 예상대로 작동하지 않습니다.

private void PrintNumbers(int[] numbers) { 
    for(int number:numbers) { 
     System.out.print(number + " "); 
    } 
    System.out.println(""); 
} 

private void swap(int[] numbers, int i, int j) { 
    int temp; 
    temp = numbers[j]; 
    numbers[j] = numbers[i]; 
    numbers[i] = temp; 
} 


private int Partition(int[] numbers, int start, int end) { 
    int i = start - 1; 
    int wall = numbers[end]; 
    int j; 
    for(j = start; j < end - 1; j++) { 
     if(numbers[j] <= wall) { 
      i++; 
      swap(numbers, i, j); 
     } 
    } 

    swap(numbers, i+1, end); 
    return i+1; 
} 

private void QuickSort(int[] numbers, int start, int end) { 
    if(start < end) { 
     int q = Partition(numbers, start, end); 
     QuickSort(numbers, start, q-1); 
     QuickSort(numbers, q+1, end); 
    } 
} 

public static void main(String[] args) { 
    int[] numbers = {2, 8, 7, 1, 3, 5, 6, 4}; 
    QS qs = new QS(); 
    qs.QuickSort(numbers, 0, numbers.length-1); 
    qs.PrintNumbers(numbers); 
}

출력은 다음과 같습니다 2 3 1 4 5 7 8 6 내가 잘못 어떤 생각?

출처

2014-11-10 user3666471

'for (j = start, j

그걸 수정 한 것 같았습니다. 그러나 이제 나는 그것이 왜 책의 '끝 -1'이었는지 궁금합니다. – user3666471

'end-1'이면 'j <= end-1'이어야합니다. 여기서 요점은 array.length가 배열의 길이를 줄 것이고, 인덱스가 0부터 시작될 때 보통 우리는 마지막 인덱스를 줄'array.length-1'을합니다. 그래서 여러분은'QuickSort'를 재귀 적으로 시작할 때 이미 그렇게하고 있습니다. –

for(j = start; j < end - 1; j++)은 for(j = start; j < end; j++)이어야합니다. 다른 것은 java에서 모든 메소드와 변수는 printNumbers와 같이 소문자로 시작해야합니다.

메인 메서드에서 처음으로 QuickSort을 호출하는 동안 매번 뺄셈 뺄 필요가 없습니다.

출처

2014-11-10 07:09:36

Quicksort가 예상대로 작동하지 않습니다.

답변

관련 문제