Here is the pseudocode straight from the book (CORMEN):

Partition(A,p,r)
        x=A[p]
        i=p-1
        j=r 1 
        while(TRUE)
            repeat
                j=j-1
            until A[j]<=x
            repeat
                i=i 1
            until A[i]>=x
            if i<j
                SWAP A[i] <=> A[j]
            else return j

Here is code in C :

#include<bits/stdc  .h>
using namespace std;


int partition(int a[], int low, int high)
{
    int pivot = a[low];
    int i = low - 1;
    int j = high   1;
    while (1)
    {
        do {
            i  ;
        } while (a[i] < pivot);

        do {
            j--;
        } while (a[j] > pivot);

        if (i >= j) {
            cout<<j<<endl;
            return j;

        }

        swap(a[i], a[j]);
    }
}


/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
        at right place*/
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi   1, high);
    }
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i  )
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int arr[] = {7,3,2,6,4,1,3,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"partition:\n";
    partition(arr,0,7);
    printArray(arr, n);

    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

If I use this array in input:

[5,3,2,6,4,1,3,7]

everything works logically well because the array returned by the partitioning will be:

[3,3,2,1,4,6,5,7] 

Termination i=5 and j=4 so my pivot is 4. And all elements to the left of 4 are minor and all to the right are major

Now if I use this array in input:

[7,3,2,6,4,1,3,5]

I will have this situation at the end of the partition

[5,3,2,6,4,1,3,7]

which will return to me as pivot j = 6 that is 3. Now the elements on the left of 3 are not all minor and on the right are major. But how is it possible that this works? Shouldn't I have the elements to the left of the pivot minor and to the right major?

CodePudding user response：

With Hoare partition the pivot and values equal to the pivot can end up anywhere. The returned index is not an index to the pivot, but just a separator. For the code above, when partition is done, then elements <= pivot will be at or to the left of j, and elements >= pivot will be to the right of j. After doing a partition step, the C code should be:

        quickSort(arr, low, pi);           // not pi - 1
        quickSort(arr, pi   1, high);

example code that includes testing of quicksort:

uint32_t Rnd32()
{
static uint32_t r = 0;
    r = r*1664525   1013904223;
    return r;
}

int Partition(int ar[], int lo, int hi)
{
    int pv = ar[lo (hi-lo)/2];
    int i = lo - 1;
    int j = hi   1;
    while(1){
        while(ar[  i] < pv);
        while(ar[--j] > pv);
        if(i >= j)
            return j;
        std::swap(ar[i], ar[j]);
    }
}

void QuickSort(int ar[], int lo, int hi)
{
    while (lo < hi){
        int pi = Partition(ar, lo, hi);
        if((pi - lo) < (pi - hi)){
            QuickSort(ar, lo, pi);
            lo = pi   1;
        } else {
            QuickSort(ar, pi   1, hi);
            hi = pi;
        }
    }
}

#define COUNT (16*1024*1024)

int main(int argc, char**argv)
{
    size_t i;
    int * ar = new int [COUNT];
    for(i = 0; i < COUNT; i  ){
        ar[i] = Rnd32();
    }

    QuickSort(ar, 0, COUNT-1);

    for(i = 1; i < COUNT; i  )
        if(ar[i-1] > ar[i])
            break;
    if(i == COUNT)
        std::cout << "passed" << std::endl;
    else
        std::cout << "failed" << std::endl;

    delete[] ar;

    return(0);
}