選択ソート単語

• 原理
• 性能検討
• 関連項目
• 掲示板

選択ソートはソートアルゴリズムの一種。

O(n^2)で遅い部類。比較回数が配列の長さのみで決まり、要素状態に左右されないという特徴がある。交換が最大で要素数-1なので移動量は少ない。
安定ソートではない。

原理

配列を順に探して一番小さな値を見つける。それを先頭の要素と入れ替えて、以下残りの部分で繰り返す。

性能検討

長さnの配列中で一番小さい値を見つけるためには、まず値を一つ記憶し、残りの要素と比較しながらより小さい値が見つかったら候補を変えるということを繰り返すので、比較回数はn-1である。よってソート全体の比較回数はn-1+n-2+...+1=n(n-1)/2となる。

交換は入れ替えが生じた場合に一回、たまたま最初から最小値だった場合に省略できる。よって最大でn-1、最小で0となり、全ソートアルゴリズムの中でも一番交換が少ないものの一つである。

この交換回数の少なさがあるため、O(n^2)組の中では最速の部類に入るものの所詮はO(n^2)。また安定ソートじゃないとか、ソート済みだろうがなんだろうが比較が減らないというお固い性質が災いして、挿入ソートのようなここぞという場面は少ない。やっぱり必殺技欲しいよな。暗黒流れ星とか。

ただ、実装のシンプルさ故に、要素数が10~20ぐらいであれば大掛かりなアルゴリズムよりも速かったりするので、他のアルゴリズムのサブとして組み込むのはまあまあ。安定性を考慮しなくていいならマージソート辺りは相性がいい。

関連項目

• ソート
• アルゴリズム

キーワード「選択ソート」でニコニコ動画を検索

タグ「選択ソート」でニコニコ動画を検索