2
$\begingroup$

Wiki states: "...partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion."

What prevents Hoare partition from not returning j equal to hi? If our pivot is max number, we may execute j <- j – 1 only once and exit with j=hi

E.g. A= [2,0]

Some implementations add a final swap of placing the initially chosen pivot into returned j:

swap A[lo] with A[j]
return j

What would guarantee p < hi?

Full pseudo-code from wiki:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1 <------------- execute once
        while A[j] > pivot

        if i >= j then
            return j <------------- exit

        swap A[i] with A[j]
$\endgroup$
1
1
$\begingroup$

Did you notice the outer loop, loop forever?


Let us say in the first iteration of that loop forever loop, we have just finished the second inner loop, do j := j - 1 while A[j] > pivot.

  • If j := j-1 has been executed at least twice, then j <= (hi+1)-2 = hi-1.

  • Otherwise j := j-1 has been executed exactly once. Then
    $\quad\quad$j = (hi+1)-1 = hi.
    Note that the first inner loop, do i := i + 1 while A[i] < pivot produces
    $\quad\quad$ i = lo
    since i = lo - 1 initially and A[lo] = pivot.

    Now we execute if i >= j then return j. Since the condition i >= j does not hold as lo < hi (the pseudocode for quicksort specifies that only when lo < hi shall partition be performed), the code return j will be skipped, i.e., we shall go on with the next iteration of that loop forever loop. In that next iteration, j := j-1 will be executed again, causing j < hi.

So, we will always have j < hi at some point of time during the partition. Since j would never increase, we will have j < hi when we return j. $\quad\checkmark$


The analysis above holds regardless of whether our pivot is the max number or not.

$\endgroup$
1
  • $\begingroup$ On the 1st iteration of the outer loop <i> always stays equal to <lo>. That means the outer loop will be executed 2 or more times. Never once. Thank you, John L. It closes my gap with different variations (old Cormen) where it starts rolling <j> prior to <i> $\endgroup$
    – belz
    Jul 5 '21 at 13:25

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.