プログラマになったはいいけど、どのソートを使えばいいかわからない…
そんなプログラマはいないかな？
今回の特集は、そんな悩めるプログラマ諸君に
お送りする「バブルソート」特集だ。
バブルソートは動作の遅い初心者向けのソート…なんて思っている人も
多いと思うけど、実はとっても奥深いソートなんだ。
確かに、遅いアルゴリズムの代表格であり、実用的ではないといわれている。
でも、それを補って余りある特性が、ソートの基本的な性能と改善の余地だ。
バブルソートは、順列に対して最速の性能を持っているんだ。
順列というのはソート済みになっている配列の事。
要素の数も少ないし、ほとんどの場合はソート済みのはずなんだけど…、
という場所で使えば非常に活躍できる。
さらに、クイックソートやヒープソートが持っていない
｢安定なソート｣という性能も見逃せない。
安定なソートというのは、要素が同じ大きさの時、
もともとの配列の前後が入れ替わらないソートをいうんだ。
例えば、トランプのカードだと、もともとが数字の順に並んでいる状態になっている時、
さらにスート(スペードやダイア)で並び替えたら
(スペード)１２３…ＪＱＫ(ダイア)１２３…と並ぶってことだね。
改善の余地にも触れておこう。
バブルソートを良く眺めると、二回目以降に無駄な比較があることに気づくかな。
最初と最後に要素を交換する場所を次回の探査に生かすことで、
大幅に無駄な比較部分を減らすことが出来る。
さらに、前から後ろ、という順だけでなく後ろから前へという
逆に探査するという方法も取り入れると、
シェーカーソート(双方向バブルソート)ってソートに派生するんだ。
理解のしやすさと作り込み勝手の良さ
これでバブルソートの魅力は伝わったかな？
さぁキミも、バブルソートを使ってみよう！