Разделение на месте, которое возвращает позицию Pivot

Question

Так как нормальный раздел возвращает индекс j такой, что каждый элемент с индексом i <= j меньше, чем выбранная точка, а каждый элемент с индексом m> j больше, чем точка, нет никаких гарантий, что j являетсястержень.Можно ли было бы создать еще один алгоритм разбиения на месте, который будет возвращать именно новую позицию поворота?Первоначально я пытался переместить поворотную ось в последнюю позицию, но это не привело к оптимальному решению.

Answer 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;
}