Selection sort

From Algowiki
Jump to: navigation, search

General information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: loop

Abstract view

Invariant: After iterations: The elements at positions are correctly placed in sorting order.

Variant: increases by .

Break condition: .

Induction Basis

Abstract view: Nothing to do.

Implementation: Nothing to do.

Proof: Nothing to show.

Induction step

Abstract view: Identify the maximum out of and then move it, by a swap, to position .

Implementation:

  1. Set
  2. For all : If set .
  3. Swap and .

Correctness: Obviously: is the maximum element out of .

Complexity

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 .