Quicksort

Quick Sort

whatever

Openlearnware

General information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: recursion

Abstract view

Invariant: After a recursive call, the input sequence of this recursive call is sorted.

Variant: In each recursive call, the sequence of the callee is strictly shorter than that of the caller.

Break condition: The sequence is empty or a singleton.

Induction basis

Abstract view: Nothing to do on an empty sequence or a singleton.

Implementation: Ditto.

Proof: Empty sequences and singletons are trivially sorted.

Induction step

Abstract view:

1. Choose a pivot value [math]\displaystyle{ p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}] }[/math] (note that [math]\displaystyle{ p }[/math] is not required to be an element of [math]\displaystyle{ S }[/math].
2. Partition [math]\displaystyle{ S }[/math] into sequences, [math]\displaystyle{ S_1 }[/math], [math]\displaystyle{ S_2 }[/math] and [math]\displaystyle{ S_3 }[/math], such that [math]\displaystyle{ x \lt p }[/math] for [math]\displaystyle{ x \in S_1 }[/math], [math]\displaystyle{ x = p }[/math] for [math]\displaystyle{ x \in S_2 }[/math], and [math]\displaystyle{ x \gt p }[/math] for [math]\displaystyle{ x \in S_3 }[/math].
3. Sort [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_3 }[/math] recursively.
4. The concatenation of all three lists, [math]\displaystyle{ S_1 \| S_2 \| S_3 }[/math], is the result of the algorithm.

Implementation:

1. Chose [math]\displaystyle{ p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}] }[/math] according to some pivoting rule.
2. [math]\displaystyle{ S_1 := S_2 := S_3 := \emptyset }[/math].
3. For [math]\displaystyle{ x \in S }[/math], append [math]\displaystyle{ x }[/math] to
   1. [math]\displaystyle{ S_1 }[/math] if [math]\displaystyle{ x \lt p }[/math],
   2. [math]\displaystyle{ S_2 }[/math] if [math]\displaystyle{ x = p }[/math],
   3. [math]\displaystyle{ S_3 }[/math] if [math]\displaystyle{ x \gt p }[/math].
4. Call Quicksort on [math]\displaystyle{ S_1 }[/math] giving [math]\displaystyle{ S_1' }[/math]
5. Call Quicksort on [math]\displaystyle{ S_3 }[/math] giving [math]\displaystyle{ S_3' }[/math]
6. Return [math]\displaystyle{ S_1' \| S_2' \| S_3' }[/math].

Correctness:

By incuction hypothesis, [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_3' }[/math] are sorted permutations of [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_3 }[/math], respectively. In particular [math]\displaystyle{ S_1' \| S_2 \| S_3' }[/math] is a permutation of [math]\displaystyle{ S }[/math]. To see that this permutation is sorted, let [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] be two memebers of [math]\displaystyle{ S }[/math] such that [math]\displaystyle{ y }[/math] immediately succeeds [math]\displaystyle{ x }[/math] in the resulting sequence [math]\displaystyle{ S_1' \| S_2 \| S_3' }[/math]. We have to show [math]\displaystyle{ x \leq y }[/math].

1. If [math]\displaystyle{ x,y \in S_1' }[/math] or [math]\displaystyle{ x,y \in S_3' }[/math], [math]\displaystyle{ x \leq y }[/math] resultes from the induction hypothesis.
2. On the other hand, if [math]\displaystyle{ x,y \in S_2 }[/math]. It is [math]\displaystyle{ x = y = p }[/math], which trivially implies [math]\displaystyle{ x \leq y }[/math]
3. Finally, for following cases, [math]\displaystyle{ x \leq y }[/math] is implied by the specific way of partitioning [math]\displaystyle{ S }[/math] into [math]\displaystyle{ S_1' }[/math], [math]\displaystyle{ S_2 }[/math] and [math]\displaystyle{ S_3' }[/math]:
   1. [math]\displaystyle{ x \in S_1' }[/math] and [math]\displaystyle{ y \in S_2 }[/math]
   2. [math]\displaystyle{ x \in S_2 }[/math] and [math]\displaystyle{ y \in S_3' }[/math]
   3. [math]\displaystyle{ x \in S_1' }[/math] and [math]\displaystyle{ y \in S_3' }[/math]

Obviously, this case distinction covers all potential cases, so the claim is proved.