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.

  • $\begingroup$ 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). $\endgroup$ – Luke Mathieson May 19 '14 at 10:47
  • 4
    $\begingroup$ 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. $\endgroup$ – D.W. Jun 18 '14 at 13:08

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[4]$ 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.