はじめに
本記事では、バブルソートについて記述します。
ふと知らない単語が私の元に来たので、調べてアウトプットします。
バブルソートとは
データ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、
端から順番に隣接する要素同士を比較・交換していくもの。
ソートを実行すると値の大きいまたは小さい要素が泡みたいに浮かびあがってくるように見えることから、
バブルソートと呼ばれるらしいです。
アルゴリズムについて
リスト（今回なら数列）を昇順に整列させる手順。
① ⑨ ④ ② ⑤ ⑦
1.先頭の①と隣の⑨を比較する
2.今回は、昇順ですので、①は⑨より小さいため、交換はしません。
3.次に2番目の⑨に焦点を当てます。⑨は④よりも大きいため、ポジションを交換します。
① ④ ⑨ ② ⑤ ⑦
4.このように次は、３番目になった⑨を焦点にし、⑨と②を比較する。次は⑨と⑤を比較する。次は...
① ④ ② ⑤ ⑦ ⑨
5.このようにして終末まで繰り返します。
6.次は④と②を比較します。
.
.
.
① ② ④ ⑤ ⑦ ⑨
このような流れで数列の大小が整うということですね。
特徴
以下の記事にて詳しく説明されていたため、参照します。
バブルソート 一番参考になった記事
リストの個数を n とすると、バブルソートは必ず
n(n - 1)/2 回のスキャンが行われます。
n 個のリストがある場合、1回目で1番目に重い(大きい)値がリストの終端に移動してゆき、2回目のスキャンで2番目に重い値を浮かびあがらせ、3回目のスキャンで・・・、という具合に n 回のスキャンで n 番目に重い値を浮かびあがらせるのがバブルソートの特徴です。 (条件を入れ換えると「軽い(小さい)値を浮かびあがらせる」と述べることができます)
リストの個数が多くなればなるほど処理速度も遅くなりますが、シンプルなアルゴリズムなのでデータ量が少ないときには手軽に実装できます。
終わりに
バブルソートという仕組み自体は、簡単に思えますが、
バブルソートという言葉を知らなかったです。
まだまだ知らない単語が出てくるので、１つ１つ潰して理解していきます。
今回の参考サイト
バブルソート qiita記事
バブルソート 一番参考になった記事
バブルソート 【bubble sort】 単純交換法 / 隣接交換法 / 基本交換法
バブルソート ruby
明日も頑張ります！