クイックソートアルゴリズムで再帰関数がどのように終了しましたか？

Question

私はクイックソートアルゴリズムのこの再帰関数がどのように動作するかを知るために、ブレークポイントを扱おうとしました。

static public void SortQuick(int[] arr, int left, int right) 
    { 
     if (left < right) 
     { 
      int pivot = Partition(arr, left, right); 

      if (pivot > 1) 
      { 
       SortQuick(arr, left, pivot - 1); 
      } 

      if (pivot + 1 < right) 
      { 
       SortQuick(arr, pivot + 1, right); 
      } 
     } 
    } 

私が知りたいのは、2つの内側の「if文」が偽になるときに何が起こっているかです。なぜ再帰が終了しないのですか？次のプロセスはどこに行くのでしょうか？

私がブレークポイント を段階的に実行しようとすると、実際に何が起こったのか分かりませんでした。左= 0 と右= 2ですが、私がブレークポイントに従うと、 は左になりました= 5、右= 9とにかく、4は私の最初のピボットで、私は に10の数字を入力しました。だから、基本的に、私はコードが のパーティションを開始していたことを知っていました。だから、 左変数が5になり、右が9になったのです。 これが起こり、この関数のどの部分が左に= 05と右= 9左= 0かつ右= 2であるかを取得しません。

これは私が入力したものです：（5 1 9 2 3 8 4 7 6 10）

私はすでにパーティションのプロセスを理解してきたので、私は私の質問の中に含まれていませんでした。前もって感謝します。 :)

Answer 1

再帰関数には常に2つのケースが必要であると教えられます。再帰的ケースと終端ケースです。よく分からないのは、終了ケースに必要なのはであり、を再発しないことです。再帰グラフのリーフノードで

、あなたはleft < rightが真でないコール（例えばleft == 0とpivot == 1はSortQuick(arr, 0, 0)を呼び出すにつながる）があり、機能はポイントにノーオペレーション（以上、それは再帰せずに終了していますさらに）。

Answer 2

コードは、修正が必要な、固定されたラインがコメントされている：

static public void SortQuick(int[] arr, int left, int right) 
    { 
     if (left < right) 
     { 
      int pivot = Partition(arr, left, right); 

      if (pivot - 1 > left) // this line fixed 
      { 
       SortQuick(arr, left, pivot - 1); 
      } 

      if (pivot + 1 < right) 
      { 
       SortQuick(arr, pivot + 1, right); 
      } 
     } 
    } 

パーティション（）明らかにピボット指標として（ハイ+ロー）/ 2を選択します。プログラムは最初にデータの深さをソートします。最初のインスタンスは== 0、右== 9のため、パーティションは（0 + 9）/ 2 = 4を返します。次のインスタンスは== 0、right == 3を残しているので、Partitionは2を返します。 = 0、right = 1、pivot = 1、これは基本ケースであるため、SortQuickはただ返します。 2 + 1のピボットは< 3ではないので、これも基本ケースなので、SortQuickは再び戻ります。次のインスタンスは、左= 5、右= 9、ピボット= 7です。ここからその部分を追跡できるかどうかを確認してください。

（ピボット - 1 < =左）または（ピボット+ 1> =右）、パーティションサイズが2または3の場合、基本ケースが発生します。この場合、Partition（）は元の配列、SortQuickだけが返されます。

これは右> =左ならば、それは内側の2つに偽になった場合、「if文」の次のプロセスが行く場所を[OK]を、再帰は、その後...終了します

How the recursion in Quicksort algorithm works?