アルゴリズム
の順に以下の操作を行う.
> を比較し, ならば要素を入れ替える.
正当性
のとき,最大要素が に移動する. のとき,次に大きい要素が に移動する.以下,帰納的に成り立つ.
計算量
より .
アルゴリズム
正当性
帰納的に示す. が正しくソートされていると仮定する.このときステップ 3 で の要素を昇順に並べた配列,すなわち のソート済み配列が得られる.
計算量
漸化式 より, となる.
の全域木 に対し,「 が最小木 任意の補木辺 に対し, によって定まる基本閉路を とすると, ならば 」
必要性()の証明
ある辺 について と仮定する.このとき を考えると である.また は全域木である.( 路が を使っていた場合,代わりに を使えばよい.)よって, の最小性に矛盾.
十分性()の証明
を右辺の条件を満たし最小木でない全域木とする.また, を が最小になるような最小木とする.ある辺 を取りその端点を とすると, は を つの連結成分 に分割する.また, の基本閉路 を考えると, 上には端点がそれぞれ に含まれるような辺 が存在する.仮定より, である.ここで, とすると, かつ が全域木であることから は最小木.したがって の最小性に矛盾.
mermaid.js