Quicksort: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
|||
| Line 9: | Line 9: | ||
</div> | </div> | ||
== General | == General information == | ||
'''Algorithmic problem:''' [[Sorting based on pairwise comparison]] | '''Algorithmic problem:''' [[Sorting based on pairwise comparison]] | ||
'''Type of algorithm:''' recursion | '''Type of algorithm:''' recursion | ||
== Abstract | == Abstract view == | ||
'''Invariant:''' After a recursive call, the input sequence of this recursive call is sorted. | '''Invariant:''' After a recursive call, the input sequence of this recursive call is sorted. | ||
| Line 22: | Line 22: | ||
'''Break condition:''' The sequence is empty or a singleton. | '''Break condition:''' The sequence is empty or a singleton. | ||
== Induction | == Induction basis == | ||
'''Abstract view:''' Nothing to do on an empty sequence or a singleton. | '''Abstract view:''' Nothing to do on an empty sequence or a singleton. | ||
| Line 40: | Line 40: | ||
== Complexity == | == Complexity == | ||
== Further | == 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.