Quicksort: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 51: Line 51:


=== Correctness: ===
=== Correctness: ===
By incuction hypothesis, <math>S_1'</math> and <math>S_3'</math> are sorted permutations of <math>S_1</math> and <math>S_3</math>


== Complexity ==
== Complexity ==


== Further information ==
== Further information ==

Revision as of 13:57, 2 October 2014

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]

Complexity

Further information