クイックソートのピボットとしての最初の要素

Question

なぜこのコードが間違っていますか？私は紙の上で、何が間違っていないことをトレースしている

：クイックソートでは、私は、ピボットとして最初の要素を取り上げています。

private void QuickSort(ref int [] S ,int l,int h) 
    { 
     //partioning 
     int pivot_index = l; 
     int j = 0; 
     int temp = 0; 
     for(int i=l+1;i<=h;i++) 
      if (S[pivot_index] > S[i]) 
      { 
       j++; 
       temp = S[i]; 
       S[i] = S[j]; 
       S[j] = temp; 
      } 
     pivot_index = j; 
     temp = S[l]; 
     S[l] = S[j]; 
     S[j] = temp; 
     //end partioning 

     if (l < h && pivot_index>l && pivot_index<h) 
     { 
      QuickSort(ref S, l, pivot_index - 1); 
      QuickSort(ref S, pivot_index + 1, h); 
     } 
    } 

はここに私のメインです：

 int[] List = get_input(textBox1.Text, ref n); 
     // 
     QuickSort(ref List, 0, n-1); 

Answer 1

あなたの機能は明らかに、アレイ内の[l, h]範囲を並べ替えることになっている、まだいくつかの理由のためにあなたは、要素数jと要素番号iを交換しています。後者（j）は[l, h]の範囲外です（常に最初は0で、1,2,3などとなります）。これで何をしようとしていますか？なぜあなたのソート範囲から離れて、全く関係のない遠隔地にあなたの要素を交換していますか？

言い換えれば、これはでもリモートで私にソートアルゴリズムクイックソートスタイルのようには見えません。 jで説明できない操作は、実装が実際に何かをソートできない1つの理由です。

Answer 2

あなたのアルゴリズムは間違っています。ピボット値int pivot = S[pivot_index];を取得します。

次に、スワップする2つの要素を決定します。したがって、左からピボット値以上の最初の要素を決定します。これはiとなります。その後、右からピボット値以下の最初の要素を決定します。これはjとなります。 iがjスワップS[i]およびS[j]未満である限り、このプロセスを繰り返します。あなたは再帰的クイックソートを呼び出すことができる場合に見える、作るためにこれ以上のスワップがないだけ後

。ここでは、左部と右部の2つのチェックが必要です。

---

また、中央の要素をピボット要素として使用する方がよいことに注意してください。要素があらかじめソートされているかソート順にソートされている場合は、QuickSortのパフォーマンスが向上します。

int pivot = S[(l+h)/2];