If n = 1, Since only one element is there the algorithm is correct.
It is correct on lists of size smaller than n. So algorithm is correct for list smaller than size n .
After positioning, the pivot p at position i; i = 1, . . . , n − 1, splits a list of size n into the head sublist of size i and the tail sublist of size n − 1 − i. Elements of the head sublist are not greater than p. Elements of the tail sublist are not smaller than p. • By the induction hypothesis, both the head and tail sublists are sorted correctly. • Therefore, the whole list of size n is sorted correctly.
We will prove the correctness using loop invariant.
Let (S, a, b) be any input to inPlacePartition and let c be the output of Partition on this input. Suppose 1 ≤ a < b.
Let x = A[b].
at the beginning of the for-loop, for all k, a ≤ k ≤ b, the following properties hold:
1. If a ≤ k ≤ i, then A[k] ≤ x.
2. If i + 1 ≤ k ≤ j − 1, then A[k] > x.
3. If k = b, then A[k] = x
The initial value of i is a − 1 and the initial value of j is a. So, there is no k such a ≤ k ≤ i and there is no k such that
i + 1 ≤ k ≤ j − 1. Thus, the first conditions are met. The initial value of A[b] = x, is so the last one is met.
Suppose that the three conditions are met at the beginning and that j ≤ b − 1.
Suppose that A[j] > x. The value of i will not be changed, so (1) holds. The value of j becomes j + 1. Since A[j] > x, (2) will for the new value of j. Also, A[b] is unchanged so (3) holds. Suppose that A[j] ≤ x. Then A[i + 1] and A[j] will be exchanged. By (2), A[i + 1] > x. So, after exchange A[i + 1] ≤ x and A[j] > x. Both i and j will be incremented by 1, so (1) and (2) will be preserved. Again (3) still holds.
At the end, j = b. So, for all k, 1 ≤ k ≤ i, A[k] ≤ x and for all k, i + 1 ≤ k ≤ b − 1, A[k] > x.
So the Quick Sort algorithm is proved to be correct in loop entrance , while in the loop and after termination of the loop.Hence Proved.