1
$\begingroup$

Recently I’ve studied QuickSort and understood its general idea.

Basically, we do the following:

  1. Pick an element from the array (no matter which one and how in this context)
  2. Rearrange elements in the array so that elements less than the pivot are placed prior to it (in the left part of the array), and ones that are greater than the pivot are placed after it (in the right part).
  3. Apply these procedures to the left and right parts of the array.

Everything looks quite clear, but my question is: why does it eventually sorts the entire array?

I’ve read lots of articles about the QuickSort, but none of them provides a clear proof that algorithm does really work in a way they describe. So I’m looking for such a proof.

I realize that:

  • Array of one element (i.e with length 1) is already sorted.
  • After any partition the pivot is placed on it’s final position.

So what’s the proof of the fact that after applying QuickSort procedure to a given array of length N its elements will be ordered after a procedure completes?

P.S. I’ve seen several proofs based on mathematical induction. Unfortunately, I’m not familiar with it yet, so I’m primarily looking for non-induction proof.

Here they are:

$\endgroup$
  • 3
    $\begingroup$ Fundamentally all propositions of the form "something about $n$ is true for all natural number $n$" have to be proved by mathematical induction or something equivalent to it. There is no other rigorous way. You might get some intuition by small examples or experiments, which should enhance your (future) conviction that mathematical induction is both the natural way and the powerful way to go. $\endgroup$ – Apass.Jack Jan 17 at 22:31
  • 1
    $\begingroup$ @Apass.Jack thanks for the response, I’ll try to master induction method. $\endgroup$ – V. Astakhov Jan 17 at 22:42
  • $\begingroup$ The first two references you listed, one by Doina Precup and one by the great users here are pretty good. The third one can be read later when you are into Lisp. Before reading all of those, it should be nice to review the basic stuff about mathematical induction and do a few or many exercises if you are not comfortable with the basic idea and intuition of or behind mathematical induction. $\endgroup$ – Apass.Jack Jan 17 at 22:49
  • $\begingroup$ "After any partition the pivot is placed on it’s final position." -- perhaps you can combine this with the belief that any element in the array will eventually be a pivot? $\endgroup$ – Mees de Vries Jan 18 at 16:57
1
$\begingroup$

First, you need to write down your algorithm that you call "Quicksort" precisely. The devil is in the detail, and if your code doesn't get the details right, then it won't sort correctly (or you won't be able to prove that it sorts).

And then you need to use complete induction: Take the induction statement S(N) "My algorithm will sort any subarray with n ≤ N items correctly". The more obvious statement S'(N) "My algorithm will sort any subarray with N items correctly" isn't strong enough.

Next you prove S(1): If the array has 0 or 1 elements, does your algorithm sort it correctly? Most implementations will check that there are two or more elements as their very first step, and subarrays with 0 or 1 elements are sorted, so this should be no problem.

Then you need to prove that S(N) implies S(N+1). If S(N) is true, then any subarray of size n ≤ N will be sorted correctly, so only the case of an array with N+1 elements needs to be handled. Here you have to prove that one Quicksort step will divide an array of N+1 into two subarrays of size ≤ N, with each element of the left subarray <= each element of the right subarray, and no overlap.

PS You will always end up with an induction proof, more or less disguised. For example: Assume there is an array that doesn’t get sorted correctly by Quicksort. If there is any array, then there must be a smallest array that doesn’t get sorted. Take that array, pick the pivot and create two sub arrays, a left one and a right one. Sort both sub arrays with Quicksort. Since they are both smaller than the smallest array that isn’t sorted correctly, they will be sorted correctly. So Quicksort works.

That’s a property of the integers: if a set of positive integers is not empty, then it has a smallest element. Take the set of all sizes of arrays that are not correctly sorted by Quicksort. If that set is not empty, then it has a smallest element, and therefore there is a smallest array that cannot be sorted. And then you prove that the smallest array that cannot be sorted can indeed be sorted, so your assumption that some array cannot be sorted was wrong.

$\endgroup$
0
$\begingroup$

I'm not sure you actually need induction (in the sense that we try to prove $P(n+1)$ assuming $P(n)$) for the quicksort proof.

Let $(a_i)_{0 \leq i \leq n}$ be your initial array. Let $(a_{q(i)})_{0 \leq i \leq n}$ be the sorted array.

In order to prove that quicksort correctly sorted the array, we have to prove that for every pair of elements $a_i$, $a_j$ such that $a_i < a_j$, we have $q(i) < q(j)$.

For that, you need to show that:

  1. If $a_i < a_j$, $a_i$ and $a_j$ will eventually find themselves on different sides of a pivot (with $a_i$ to the left and $a_j$ to the right).

  2. Once two elements are on different sides of a pivot, their respective order stays the same until the end of the algorithm.

$\endgroup$
  • $\begingroup$ It could also be that one of $a_i,a_j$ is itself a pivot. $\endgroup$ – Yuval Filmus Jan 18 at 17:06
  • 1
    $\begingroup$ @RcnSc, yes, induction is needed if a proof with mathematical rigor is wanted. For example, how can you prove something will happen "eventually"? However, if what is sought is just an idea or intuition, of course there could be ways to explain the situation. $\endgroup$ – Apass.Jack Jan 18 at 19:21
  • $\begingroup$ Also, the correctness of quicksort is not proved by "proving $P(n+1)$ assuming $P(n)$". We have to use complete induction, a.k.a. strong induction. $\endgroup$ – Apass.Jack Jan 18 at 19:23

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.