1
$\begingroup$

Just out of curiousity: Both Introduction to Algorithms (Cormen et al), Wikipedia, and prior cs.stackexchange questions all present the Lomuto partition as:

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1    
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

which is a bit hard to remember. I'm wondering why the following restatement isn't used instead. Suppose we do a change of variable, with i' = i+1 and swap the two lines after "if A[j] < pivot" accordingly. In this case we have:

algorithm partition(A, lo, hi) is
pivot := A[hi]
i' := lo     
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'

so then the final statement is just

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo     
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

I know that this isn't a big improvement, but is there some reason that the presentations I've seen all use the original formulation?

Thanks!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.