c++ - クイックソートパーティションアルゴリズム

Question

void partition(int *a, int size) {
   int pivot = a[0];
   int left = 0, right = 0;
   for(left = 1, right = size-1; left <= right; left++, right--) {
       if(a[left] >= pivot && a[right] <= pivot){
           swap(left, right, a);
       }
   }
   swap(0, right, a);
}

クイックソートを適用するための準備手順として、配列を分割するこのメソッドを作成しました。このサンプルデータでテストしました。

8 2 5 13 4 19 12 6 3 11 10 7 9

正しい出力は次のようになります。

6 2 5 7 4 3 8 12 19 11 10 13 9

ただし、実際の出力は次のとおりです。

6 2 5 13 4 3 8 12 19 11 10 7 9

アルゴリズムはスワップ13する必要がありますが、上記のループ7の条件が原因で失敗します。の場合にのみインクリメントし、の場合にのみデクリメント&&したい。lefta[left] >= pivotrighta[right]<= pivot

Answer 1

ここに別のオプションがあります。元のものに少し似ています

int partition(int arr[], int left, int right)
{
    int pivot = arr[left];
    while (left != right)
    {
        if (arr[left] > arr[right])
        {
            swap(arr[left], arr[right]);
        }
        if (pivot == arr[left])
            right--;
        else // Pivot == arr[right]
            left++;
    }
    return left;
}

Answer 2

あなたは多かれ少なかれあなた自身の質問に答えました。あなたはおそらく次のようなことをしたいと思うでしょう:

void partition(int *a, int size) {
    int pivot = a[0];
    int left, right;
    for(left = 1, right = size-1; left < right; )
    {
        if(a[left] > pivot && a[right] <= pivot)
        {
            swap(left, right, a);
        }
        if(a[left] <= pivot) left++;
        if(a[right] > pivot) right--;
    }
}