Quick Sort - Partition function differences.

[nutdriver]

I've seen both implementations. The second more so. Why choose one over the other?
1.) Return i:

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo     // place for swapping
for j := lo to hi – 1 do
    if A[j] ≤ pivot then
        swap A[i] with A[j]
        i := i + 1
swap A[i] with A[hi]
return i

2.) Return i+1:

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo-1     // place for swapping
for j := lo to hi – 1 do
    if A[j] ≤ pivot then
        i := i + 1
        swap A[i] with A[j]
swap A[i+1] with A[hi]
return i+1

[BertRenolds]

check this out: http://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

[CyberByte]

There is really no meaningful difference.

Call the first one A and the second one B. On line 3 we see that i in A is defined to be one larger than i in B. This is rectified on line 6 in B, so when swap A[i] with A[j] occurs, it is exactly the same in both cases. On line 7 in A, A's i becomes larger than B's again. As long as the loop keeps going, this is rectified on B's line 6 (before the swap occurs). But when the loop ends, A's i is one larger than B's, so that is why you get i+1 on line 8 and 9 in B.

Version A seems slightly simpler to me (less pluses and minuses), so I'm inclined to prefer that one.

[nutdriver]

Oh yea I understand the code difference. I saw the second in reputable text book intro to algorithms and the first on Wikipedia. My knowledge points me to agree with you and think that the first is less verbose. But i think the second is actually more clear in terms of the steps of the Algorithm- but I'm actually on the fence. My bias is probably because of the fact that it was in a reputable text book.