Quicksort: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 30: | Line 30: | ||
'''Proof:''' Empty sequences and singletons are trivially sorted. | '''Proof:''' Empty sequences and singletons are trivially sorted. | ||
== Induction | == Induction step == | ||
=== Abstract view: === | |||
=== Implementation: === | |||
=== Correctness: === | |||
== Complexity == | == Complexity == | ||
== Further Information == | == Further Information == | ||
Revision as of 13:31, 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.