tags:

views:

77

answers:

1

Hello, 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);
}
+2  A: 

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.

Dror Helper
thanks alot for the explanation, I wonder how could you do that part with java ?
Hellnar
You couldn't, at least, not directly. Either you'd have to create a new array and copy over the values you want (expensive), or you'd modify the Partition function to take a start index. In this case, because the function modifies the array, only the latter approach will work.
Thomas