Function partition

CPP/sorting/intro_sort.cpp:33–59

Function to partition the array using Lomuto partition scheme

 
// Function to partition the array using Lomuto partition scheme
int partition(int a[], int low, int high)
{
    // Pick the rightmost element as a pivot from the array
    int pivot = a[high];
 
    // elements less than the pivot will be pushed to the left of `pIndex`
    // elements more than the pivot will be pushed to the right of `pIndex`
    // equal elements can go either way
    int pIndex = low;
 
    // each time we find an element less than or equal to the pivot, `pIndex`
    // is incremented, and that element would be placed before the pivot.
    for (int i = low; i < high; i++)
    {
        if (a[i] <= pivot)
        {
            swap(a[i], a[pIndex]);
            pIndex++;
        }
    }
 
    // swap `pIndex` with pivot
    swap (a[pIndex], a[high]);
 
    // return `pIndex` (index of the pivot element)
    return pIndex;
}
 
// Quicksort randomized partition to rearrange elements across pivot
int randPartition(int a[], int low, int high)