【アルゴリズム解説】バブルソートとは

今回は、アルゴリズムの整列問題「バブルソート」について書き溜め
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

概要

広告

バブルソート

大きい数字が泡のように浮いてくる

バブルソートとは、ソート(整列問題)に関するアルゴリズムの一つで、基本交換法ともよばれます。
隣り合う要素の大小を比較しながら整列させていきます。

バブルソートのアルゴリズム

バブルソートのアルゴリズムはWikipediaを参照する。

全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。
なおこの繰り返しは、入れ替えが起こらなくなった時点で(それ以降は何度繰り返しても変化が起こらなくなるので)中断することができる。

全要素を1つずつ比較して大きいものを右に集めていくイメージです。

バブルソートの計算量は

データ数nのときのアルゴリズム計算量はO(n^2)である。

学習用途で利用されるアルゴリズムで
ライブラリなどで採用されることはほぼ無い。

バブルソートをPython3で実装する

バブルソートをPython3実装すると下記のようになる。

(*天才による指摘はいつでも受け付けている)

バブルソートをJavaで実装する

バブルソートをJava実装すると下記のようになる。

(*天才による指摘はいつでも受け付けている)

バブルソートを説明しプログラムを書いてください。

さて、先程の説明を読んだ人は、バブルソートを説明できますね。
余裕の有る方は、好きな言語でバブルソートを実装してみてください。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。



じゃあね〜〜〜。