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
``````

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.

Thank you.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.