アルゴリズムで最初に習うであろうバブルソートについて、簡単に言葉で説明していきます。
また、Pythonでコードを書いて実行してみました。
バブルソートとは
バブルソートとは、隣り合う二つの数値を比較していき、大小関係に応じて交換を行って整列していくアルゴリズムです。
手順
リストを昇順に整列されるための手順です。
- 先頭の数値aと、それと隣り合う数値bを比較する。
- a>bであった場合、aとbの数値を入れ替える。a<bであった場合、入れ替えずそのまま。
- この作業をリストの終端まで繰り返す。
- 終端の数値はリスト内の最大値となっているので、この数値をソート済みにする。
- 手順1~4を繰り返す。
- 全ての数値がソート済みとなれば完了。
手順を見れば明らかですが、実行時間がかかるアルゴリズムのひとつです。
しかし、単純明快なアルゴリズムかつ並列処理との相性がいいので、割と使用されることもあるようです。
コード
言葉だけで説明されてもなかなか分かりづらいと思うので、自分の理解を深めるためにも実際にコードを書いてみました。
BubbleSort.py
import random
def bubbleSort(lst):
for i in range(len(lst)):
#比較作業を最後まで繰り返し、最大値をソート済みとします。（手順３,4,5）
for j in reversed(range(i+1,len(lst))):
#数値aとbを比較します。(手順１)
if lst[j-1] > lst[j]:
#数値a>bの場合、aとbの値を入れ替えます。(手順２)
lst[j-1],lst[j] = lst[j],lst[j-1]
return lst
if __name__ == "__main__":
#20個の数値をランダムに配列する
lst = list(range(20))
lst_ran = random.sample(lst,len(lst))
print("リスト整列前：")
print(lst_ran)
#ここでバブルソート実行
algo = bubbleSort(lst_ran)
print("リスト整列後：")
print(algo)
ランダムに0から19の配列を作成し、バブルソートで整列させました。
こちらを実行すると、このようになりました。
リスト整列前：
[11, 8, 19, 10, 9, 12, 4, 15, 2, 6, 17, 5, 14, 7, 0, 3, 13, 16, 18, 1]
リスト整列後：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
しっかりと整列されていますね。
まとめ
今回は、アルゴリズムのバブルソートを説明しました。
アルゴリズムにはまだまだたくさんの方法があるので、また次の機会にコード付きで紹介していきたいと思っています。