1
$\begingroup$

I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array).

I am having trouble seeing why in the inner while-loops, the condition $i \leq j$ is needed in addition to checking $M[i] \leq p$ (or $M[i] > p$).

What I've tried:

  • I tried running through several examples with equal elements, ordered elements etc.
  • I have compared this implementation to the ones given in CLRS Introduction to Algorithms in hope for hints.

What I've found out so far:

  • In the implementation given here, the Hoare partitioning scheme is used. However, the pseudocode given in the Wikipedia article does not seem to do this additional check.
  • There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are les than $p$, the first while loop would not terminate when not checking for $i \leq j$. However, that does not explain the necessity of checking $i \leq j$ in the second inner while loop.

I don't expect a complete answer but I would be very thankful if someone could point me in the right direction.

The QS implementation in question

$\endgroup$
  • $\begingroup$ Please provide a url or reference to that implementation of Hoare-partitioning Quicksort. $\endgroup$ – Apass.Jack Nov 13 '18 at 10:30
  • $\begingroup$ @Apass.Jack Unfortunately I cannot really point you to any sources other than the pseudocode given in the image above. It was given like this in the exercise and I didn't find it anywhere else. $\endgroup$ – ngmir Nov 13 '18 at 11:54
  • $\begingroup$ I am adding a traditional proof to my answer as well as making the condition explicit. It may take a while.... $\endgroup$ – Apass.Jack Nov 14 '18 at 13:06
  • $\begingroup$ Is my answer helpful enough? Have you considered accepting it? $\endgroup$ – Apass.Jack Apr 10 at 19:05
1
$\begingroup$

I am having trouble seeing why in the inner while-loops, the condition $i\le j$ is needed in addition to checking $M[i]\le p$ (or $M[i]\gt p$). The pseudocode given in the Wikipedia article does not seem to do this additional check. There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are less than $p$, the first while loop would not terminate when not checking for $i≤j$. However, that does not explain the necessity of checking $i≤j$ in the second inner while loop.

As you suspected, it is not needed to check the condition $i≤j$ in the second inner while loop.

One usual way to prove that condition is not needed is by analyzing all possible cases and establishing various invariants as well as employing the powerful tool of mathematical induction, which will probably convince anyone who can follow through the proof with enough patience. Although I have done that below, it is actually not convincing to myself because of the subtlety in the Hoare's quicksort as shown in Hoare's quicksort is deceptively simple, the devil in selecting element at index hi as pivot, a slight modification of Hoare's partitioning, what happens if both indexes land on the pivot. Even if I have checked my proof tens of times, it might still miss a corner case or two. As shown/implied by many answers at why is writing down mathematical proofs more fault-tolerant than writing computer code?, a traditional mathematical proof for a moderate computer program is probably far from fully satisfactory or fully correct in general. It is more like how we can understand/believe the program is correct in a high level.

Instead, I have written a program that tests the implementation of Hoare's quicksort with that condition removed.

Here is the testing program.

That program tests the sorting algorithm against every permutation of every possible way $n$ competitors can rank in a competition, allowing for the possibility of ties, up to a certain number of competitors.

What are all possible ways $n$ competitors can rank in a competition? Here is an example for $n=3$. There are four different sorted ranks, [1, 1, 1], [1, 2, 2], [1, 1, 2] and [1, 2, 3]. If a comparison sorting algorithm can sort all permutations of each of those four arrays, which counts to 13, it will sort any array of size 3 correctly. By the way, the number of ways $n$ competitors can rank in a competition is the Fubini numbers.

If a simple sorting algorithm like the current one does not work, it should fail for an array whose size is smaller than 8. For extra insurance, I have run that program against arrays size up to 11. These testing proves that condition is not needed.


A brief mathematical proof

Since many people would prefer a traditional proof, here is a sketch of a mathematical proof of the correctness of the implementation either with or without that additional check.

Let us assume l < r. Throughout the method, M is a constant reference to the array while l and r are constant indices. The pivot p = M[l] is constant, too. All we need to prove is that at the end of outer while loop, M[l] is the pivot, followed by elements not bigger than the pivot up to index j inclusively or no elements if l >= j, followed by all other elements, which are bigger than the pivot. (Then by mathematical induction on r - l, we can prove easily that the method does sort the subarray of M from indice r to l inclusively.)

  • We can establish the following invariant at the end of each iteration of the outer while loop.
    • Elements from l + 1 to the smaller of i and j are not bigger than the pivot
    • Elements from j + 1 to r are bigger than the pivot.
  • The first inner loop, while ( i <= j && M[i] <= p) { i = i + 1; } will find the smallest index i such that i <= j && M[i] > p or i == j+1.
  • The second inner loop, either while (M[j] > p) { j = j - 1; } or while (i <= j && M[j] > p) { j = j - 1; } will find the largest $j$ such that M[j] <= p.

    Why is the condition i <= j not necessary? Let us elaborate as here is the crux of current question.

    There are two cases at the start of this loop depending on the result of above inner loop.

    1. i <= j && M[i] > p. As we are looking for an element that is not larger than the pivot going from index j to smaller indices, the latest time we will succeed must before current i. That is, i <= j will always be satisfied throughout the loop. That is, the condition i <= j is not necessary.
    2. i == j+1. The first inner loop must have missed the above case, since j is smaller than j + 1. That means M[j] > p was not satisfied. So at the start of current loop, we have both i > j and M[j] <= p. Using either version of the second inner while loop, we will break the loop right away.
  • if (i < j) { swap(M, i, j);}. This swap extends both the left hand side of elements that is not bigger than the pivot and the right hand side of elements that is bigger than the pivot.

To tell the truth, I used program to double check various invariants and propositions in the mathematical proof.


Many further questions can be raised, which go much beyond the scope of the current question.

  • How to improve the performance of the testing problem?
  • How to reduce the number of test cases needed for a specific size?
  • Is there a way to determine rigorously an upper bound of the size of the array that need to be tested to prove the correctness of a sorting algorithm given its description?
$\endgroup$
  • $\begingroup$ Alternatively, you could avoid contributing to global warming by running incredibly many tests and prove instead, once and for all, that quicksort without the added checks is correct using e.g. Hoare logic. $\endgroup$ – Kai Nov 14 '18 at 11:14
  • $\begingroup$ @Kai, if you have followed some of the links that I have provided above, you would understand that my concern. I encourage you to come up with an answer that use mathematical proof, which might be plain and simple after all. In case you would think I do not like mathematical proof, please check my post here, here, here and here. $\endgroup$ – Apass.Jack Nov 14 '18 at 11:40
  • $\begingroup$ I don't debate that Hoare's quicksort is a decent challenge for aspiring verifiers. I once set a version of it as an assignment in a 2nd year course, with full marks for Hoare's partitioning scheme and slightly reduced marks for Lomuto's. (I say version because the student's were asked to use refinement calculus rather than Hoare logic.) I conjecture that answering any of your "further questions" positively is much harder. $\endgroup$ – Kai Nov 14 '18 at 11:57
  • $\begingroup$ The first of my "further questions" can be answered in various ways immediately. The second could be answered partially now and it is debatable when an answer is good enough. The third one is, as you conjectured and as far as I know, way much harder. $\endgroup$ – Apass.Jack Nov 14 '18 at 13:24
  • $\begingroup$ I just added a sketch of mathematical proof so that I could possibly "avoid contributing to global warming by running incredibly many tests". I love to save the environment. $\endgroup$ – Apass.Jack Nov 14 '18 at 22:05

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.