What is the store variable in the partition method (of the QuickSort algorithm) doing?

Question

I was looking at this simple implementation of the QuickSort algorithm.

I'm having trouble with the partition method. I've re-named the variables to help me understand. I understand most of the method, but there's one variable whose purpose I don't get. That's the store variable.

Here's my version of this method:

private int partition(int[] array, int startIndex, int endIndex) 
{
        int pivotIndex = getPivot(startIndex, endIndex);
        swapElements(array, pivotIndex, endIndex);

        pivotIndex = endIndex;
        int store = startIndex;

        for(int currentIndex = startIndex; (currentIndex <= endIndex - 1); currentIndex++) 
        {
            if(array[currentIndex] <= array[pivotIndex]) 
            {
                swapElements(array, currentIndex, store);
                store++;
            }
        }

        swapElements(array, store, pivotIndex);
        pivotIndex = store;
        return pivotIndex;
}

What is the purpose of the store variable? If startIndex and currentIndex are already pointing to the first index of the array, why you need store to do the same thing? What is it doing?

Answer 1

To answer your simpler question, you should be able to see that store does not remain the same as currentIndex as the iteration progresses. It is only incremented if array[currentIndex] <= array[pivotIndex] is true for a particular iteration. - so store is generally going to be smaller than currentIndex.

To answer more specifically, what is going on is that you pick a pivotIndex at the beginning that is pointing at some value. Then you are moving elements around in the table so that all of the values smaller than the pivotIndex value are before that value in the array, and all of the values greater than the pivotIndex value are after that value in the array. store is keeping track of where to move the next value that is found to be smaller than the pivotIndex value. That value is moved to the store position, and then store is incremented to move past that value and represent where the next smaller value should be placed.

At the end of the iteration, store is by design pointing to where the pivot value should be, since all values before store are less than that value, and all values after store are greater. So at the end, the pivot value is moved to the location pointed to by store, and store becomes the final index of the partitioning operation, the index pointing to the pivot value