많은 요소가있는 QuickSort가 StackOverflowError를 발생시킵니다

Question

좋은 하루! 내 quickSort 알고리즘을 실행할 때 StackOverflowError이 표시됩니다.

public void recQuickSort(int left, int right) 
{ 
    if(right-left <= 0) 
     return; 
    else { 
     long pivot = a[right]; 
     int partition = partitionIt(left, right, pivot); 
     recQuickSort(left, partition-1); 
     recQuickSort(partition+1, right); 
    } 
} 
public int partitionIt(int left, int right, long pivot) { 
    int leftPtr = left - 1; 
    int rightPtr = right; 
    while (true) { 
     while (a[++leftPtr] < pivot) ; 
     while (rightPtr > 0 && a[--rightPtr] > pivot) ; 
     if (leftPtr >= rightPtr) 
      break; 
     else 
      swap1(leftPtr, rightPtr); 
    } 
     swap1(leftPtr, right); 
     return leftPtr; 
} 

public void swap1(int dex1, int dex2) // Permutation of two elements 
{ 
    long temp; 
    temp = a[dex1]; 
    a[dex1] = a[dex2]; 
    a[dex2] = temp; 
} 

가 어떻게이 오류 요소> 50 000을 수정할 수 있습니다 이 오류는 다음과 같습니다 배열> 50 000

내 코드에서 때 요소를 발생?

Answer 1

작은 파티션에서 재귀 만 수행 한 다음 왼쪽 또는 오른쪽으로 업데이트하고 큰 파티션을 루프 백합니다. 이렇게하면 스택 오버플로 (log2 (n) 스택 프레임 제한)가 방지되지만 최악의 시간 복잡도 O (n^2)는 방지되지 않습니다.

public void recQuickSort(int left, int right) 
{ 
    while(true){ 
     if(right-left <= 0) 
      return; 
     else { 
      long pivot = a[right]; 
      int partition = partitionIt(left, right, pivot); 
      if((partition - left) <= (right - partition)){ 
       recQuickSort(left, partition-1); 
       left = partition+1; 
      } else { 
       recQuickSort(partition+1, right); 
       right = partition-1; 
      } 
     } 
    } 
}