Quicksort Java 코드가 무한 루프로 바뀝니다

Question

아래의 빠른 정렬 코드를 실행하려고하면 루프가 무한 루프가됩니다. 마지막 반복은 무한 루프가됩니다.

class QuickSort { 
    public static void main(String[] args) { 
     int arr[] = {10, 7, 8, 9, 1, 5,2}; 
     QuickSort ob = new QuickSort(); 
     ob.sort(arr, 0,arr.length-1); 
     for(int s:arr){ 
      System.out.print(" "+s); 
     } 
    } 
    int partition(int[] arr,int l,int h){ 
     int piv = arr[h]; 
     int i=l-1; 
     for(int j=l;j<=h-1;j++){ 
      if(arr[j] <= piv){ 
       i++; 
       int temp = arr[i]; 
       arr[i]=arr[j]; 
       arr[j]=temp; 
      } 
     } 
     int tp = arr[i+1]; 
     arr[i+1]=arr[h]; 
     arr[h]=tp; 
     return i+1; 
    } 

    void sort(int[] arr,int l,int h){ 
     while(l<h){ 
      int p = partition(arr, l, h); 
      sort(arr, l, p-1); 
      sort(arr, p+1, h); 
     } 

    } 
} 

어디에서 잘못 되었나요?

Answer 1

l 및 hsort()에서 절대 변경되지 않는다, 그래서 당신은 항상 l < h == true

Answer 2

대신 while 루프를해야합니다, 다음과 같이 if 조건을 사용합니다.

if(l<h){ 
     int p = partition(arr, l, h); 
     sort(arr, l, p-1); 
     sort(arr, p+1, h); 
    } 

무한 while 루프에서 일종의 재귀 적으로 호출 할 필요가 없습니다. 루프는 무한합니다. 왜냐하면 l과 r이 절대로 변경되지 않기 때문입니다.

희망 당신은 정렬 방법 while 사용했습니다 도움말 :

Answer 3

. 결과적으로 무한 재귀 호출은 결국 StackOverFlowException이됩니다. 주석에서 제안 된 바와 같이, 이것은 흔히 저지르는 실수이며 디버깅 (또는 간단한 알고리즘의 경우 간단한 드라이 런)을 통해 쉽게 찾을 수 있습니다.

당신은 당신이 아래 while 루프하는 것은 아니고 if 조건을 필요로 두 개의 재귀 호출이 조건이 들어 (l < h) 을 만족하는 방법 sort의 각 호출을 형성해야합니다.

void sort(int[] arr,int l,int h){ 
    if(l<h){ 
     int p = partition(arr, l, h); 
     sort(arr, l, p-1); 
     sort(arr, p+1, h); 
    } 
}