多くの要素を含むQuickSortが原因でStackOverflowErrorが発生する

Question

おはよう！クイックソートアルゴリズムを実行するときにStackOverflowErrorが表示されます。 配列内の要素は> 50 000

私のコードは、以下の場合に、このエラーが発生します。

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私はこのエラーを解決することができますか？

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; 
      } 
     } 
    } 
}