Algorithmic problem: Sorting based on pairwise comparison
Type of algorithm: loop
Invariant: After iterations: The elements at positions are correctly placed in sorting order.
Variant: increases by .
Break condition: .
Abstract view: Nothing to do.
Implementation: Nothing to do.
Proof: Nothing to show.
Abstract view: Identify the maximum out of and then move it, by a swap, to position .
- For all : If set .
- Swap and .
Correctness: Obviously: is the maximum element out of .
Statement: The asymptotic complexity is in in the best and worst case, where is the complexity of the comparison.
Proof: The asymptotic complexity of the -th iteration is in . Therefore, the total complexity is in .