ピボット位置を返す場所のパーティション

Question

通常のパーティションでは、インデックスがi= jの各要素がchoisenピボットより小さく、インデックスm> jの各要素がピボットより大きいjがピボットであるという保証はない。正確に新しいピボット位置を返す場所パーティションアルゴリズムを別の場所に作成することは可能でしょうか？ 最初は、最後のポジションでchoisenピボットを動かす必要がありましたが、最適な解決には至りません。

Answer 1

重要なことは、スワッピングのピボットを外しておくことです。ただし、境界線の1つに戻し、最後に正しい場所にスワップするときは、最初の点を除きます。

int partition(int *A, int low, int high) { 

    if (high <= low) return low; // in that case, partition shouldn't be called, but cater for it 

    int pivot_position = low; // or high, or low + (high-low)/2, or whatever 
    int pivot = A[pivot_position]; 

    A[pivot_position] = A[high]; 
    A[high] = pivot; // these two lines are unnecessary if pivot_position == high 
    int i = low, j = high-1; 

    while(i < j) { 

     while(i < j && A[i] <= pivot) 
      ++i; // i == j or A[i] > pivot, and A[k] <=pivot for low <= k < i 

     while(i < j && A[j] > pivot) 
      --j; // i == j or A[j] <= pivot, and A[m] > pivot for j < m < high 

     if (i < j) { 
      int temp = A[j]; 
      A[j] = A[i]; 
      A[i] = temp; 
     } 
    } 
    if (A[i] <= pivot) 
     ++i; 

    // now A[k] <= pivot for low <= k < i and A[m] > pivot for i <= m < high 
    A[high] = A[i]; 
    A[i] = pivot; 
    return i; 
}