CODEWITHSUNDEEP
algorithmpivotquicksortdivide-and-conquerdata-partitioning
gr1ph00n
gr1ph00n

Reputation: 65

An in place Partition which returns the Pivot position

Since a normal partition returns an index j such that each element with index i <= j is less than the choisen pivot, and each element with index m > j is bigger than the pivot, there are no guarantees that j is the pivot. Would it be possible to create another in place partition algorithm which returns exactly the new pivot position? Initially, I tought of moving the choisen pivot in the last position, but it does not lead to an optimal solution though.

Upvotes: 0

Views: 2516

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183888

The key is to keep the pivot out of the swapping, except at the very beginning when you store it away at one of the boundaries and at the end when you swap it into its correct place.

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

Upvotes: 1

Related Questions