# Quicksort implementation unclear

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.

• You example just gives a degenerate case where storeIndex is incremented at every step. Try one with a pivot value that is about in the middle of the values (also, more than four values would give a better idea). – Luke Mathieson May 19 '14 at 10:47
• What's the question? "It is not clear for me why it is true" - what what is true? I read the entire question and I can't figure out precisely what your question is. – D.W. Jun 18 '14 at 13:08

## 1 Answer

Consider $A = [5,2,7,6,3,4]$ and $pivotValue=5$. After pushing $5$ to end we get $A=[4,2,7,6,3,5]$. Now when $i=2$, the $storeIndex$ is not changed. Similar is the case for $i=3$. When $i=4$, $A$ and $A[storeIndex]$ get swapped. Note that $storeIndex=2$. So we get $A=[4,2,3,6,7,5]$. You can think $storeIndex$ as a 'marker'. After each iteration of $for$ loop, all values upto 'marker' index are smaller than $pivotValue$.

• First swap happens outside of the loop before incrementing i variable, so i=0 in your case after first swap – mulder May 19 '14 at 10:22