This code is taken from wikipedia:
// left is the index of the leftmost element of the subarray // right is the index of the rightmost element of the subarray (inclusive) // number of elements in subarray = right-left+1 function partition(array, left, right, pivotIndex) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] storeIndex := left for i from left to right - 1 if array[i] ≤ pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place return storeIndex
It is not clear for me why it is true, every iteration storeIndex and i index are pointing to the same place as I see it.
Where am I wrong?
Lets Take for example the array 9,8,6,5
1.pivotIndex I chosen is 0, hence pivot value is 9.
2.After first swap out array is : 5,8,6,9 (storeIndex point to 0)
3. entering loop left pointing to 0 index, condition happens that is why we swaping on the same cell.
4. i is incremented and pointing to 1, also store index is 1 and so on.