Hellnar
Hellnar

Reputation: 64883

A newbie C question

I am trying to understand a code, what exactly &(ipA[iLower + 1] stands for in the below code (partition function of a quicksort?

void Partition(int* ipA, int iSize) {

    // Partitions of size 0 or 1 are already sorted
    if (iSize <= 1) {
        return;
    }

    // Select a pivot from the array randomly
    int iPivot = ipA[rand() % iSize];

    // Indices of the entries to be swapped
    int iLower = 0;
    int iUpper = iSize - 1;

    // Partition array into sections above and below the pivot
    while (iLower < iUpper) {

        while (ipA[iLower] < iPivot) {
            ++iLower;
        }

        while (ipA[iUpper] > iPivot) {
            --iUpper;
        }

        // Swap the entries at the lower and upper indices
        int iTemp       = ipA[iLower];
        ipA[iLower]     = ipA[iUpper];
        ipA[iUpper]     = iTemp;
    }

    // Recursively call partition on each partititon.
    Partition(ipA, iLower);
    Partition(&(ipA[iLower + 1]), iSize - iUpper - 1);
}

Upvotes: 1

Views: 147

Answers (1)

Dror Helper
Dror Helper

Reputation: 30819

The method Partition is called from Partition each time the array passed is split to two arrays one from the beginning of the current array and one from the index of iLower + 1.

& means the address of (pointer) so the call &(ipA[iLower + 1] is like calling a new array (a pointer in C/C++) from the address of the cell insinde ipA at index iLower + 1.
Because passing arrays in C is done by passing the pointer to their start it's effectivly passing an array that starts in that address.

Upvotes: 2

Related Questions