テイル再帰を伴うC++クイックソート

Question

Hy人、

クイックソートでC++で何か問題があります。並べ替えられた配列（値の増加または減少）の最悪の場合、〜900要素の配列でスタックオーバーフローが発生します。末尾再帰は、私が見つけた解決策だったが、イムはおそらくイム任意の改善をachivingわけではないので、右ここでそれをしない：

void quickSort(int *array, int start, int end){ 
    //elementary state 
    if (start + 1 > end){ 
     return; 
    } 

    //partitioning, retuns position of pivotelemnt 
    int wall = partitioning(array, start, end); 

    //recursion 
    quickSort(array, start, wall-1); 
    //tail recursion? 
    return quickSort(array, wall + 1, end); 
}//quickSort 

this Wikipedia article後、私はそこに最初の例として、クイックソートの私の最後の呼び出しへの復帰を追加しました。再帰、 - （壁側）対 - （開始の壁）、スタックオーバーフローを避けるために

int partitioning(int *array, int start, int end){ 

    //partitioningborder 
    int wall = start; 

    for (int i = wall; i < end; ++i){ 
     if (array[i] <= array[end]){ 

      //swap an element if needed 
      int swap = array[i]; 
      array[i] = array[wall]; 
      array[wall] = swap; 

      //increment the partitioningborder 
      wall++; 
     }//if 
    }//for 

    //place pivotelement 
    int swap = array[end]; 
    array[end] = array[wall]; 
     array[wall] = swap; 

     return wall; 
}//partitioning 

Answer 1

、コードは、パーティションサイズを、比較する必要がある：私は...しかし

編集を何かをやっていると思ういけません小さいパーティションでは、大きなパーティションに対してループバックします。それは本当にテール再帰ではありません。

void quickSort(int *array, int start, int end){ 
    while(start < end){ 
     wall = partition(...); // wall = index to pivot 
     // recurse on smaller part, loop on larger part 
     if((wall - start) <= (end - wall)){ 
      quickSort(a, start, wall-1); 
      start = wall+1; 
     } else { 
      quickSort(a, wall+1, end); 
      end = wall-1; 
     } 
    } 
} 

Hoareタイプのパーティション方式を使用している場合、wallまたはwall + 1はピボット値を指すことがあります。ピボット値の前に1を指すのではなく、返されたインデックスが常にピボット値を指すように、パーティションにチェックを追加できます。