Question about this quick sort example

[NoUserNameHere]

In the graphic representation of Hoare's parititon:
http://i.imgur.com/OtMaNsn.png

Why does 'j' decrement by 1 when 'i' reaches 6? Since A[j] <= pivot and A[i] >= pivot at that point, shouldn't A[i] swap with A[j]? I am a bit confused about this part.

The pseudo code I am following is this:

//Partition array from A[p] to A[r] with pivot A[p]
//Result: A[i] ≤ A[j] for p ≤ i ≤ q and q + 1 ≤ j ≤ r

x = A[p] 
i  = p - 1
j  = r + 1
while true  // infinite loop, repeat forever
    repeat j = j - 1 
         until A[j] <= x
    repeat i = i +1 
         until A[i] >= x
    if  i < j 
            swap A[i] <-> A[j]
    else  return j

[mike_2000_17]

Partitioning / sorting algorithms generally require a strict weak ordering. Meaning that it cannot be symmetric in the sense of less-or-equal on one side and greater-or-equal on the other side, as it is in your pseudo-code, because it would mean that there are "equal" elements that could go on either side. Normally, you partition by less-than on one side and not less-than on the other. And, obviously, on that picture 5 is not less-than the pivot (5) which means that it should go on the "greater-than-or-equal" side of the partitioning. In other words, here is the corrected pseudo-code:

//Partition array from A[p] to A[r] with pivot A[p]
//Result: A[i] ≤ A[j] for p ≤ i ≤ q and q + 1 ≤ j ≤ r

x = A[p] 
i  = p - 1
j  = r + 1
while true  // infinite loop, repeat forever
    repeat j = j - 1 
         until A[j] < x
    repeat i = i +1 
         until !( A[i] < x )
    if  i < j 
            swap A[i] <-> A[j]
    else  return j

You can see how the above also has the advantage of relying only on one comparison operator (less-than), which is typical of most implementations. Most generic implementations allow you to specify any strict weak ordering comparison function (e.g., less-than, greater-than, lexicographic ordering (e.g., alphabetic order), etc.), for example, the C++ std::sort function.

[NoUserNameHere]

Thank you.