はじめに
最近データ構造とアルゴリズムの学習を始めたのでアウトプットも兼ねて、誰かの役に立てればと思い、この記事を投稿するに至りました。ちなみに、言語はPythonを使います。ロジックのみに触れるため計算量には触れません。
今回はバブルソートについて紹介したいと思います。
バブルソート(bubble sort)とは
バブルソートとは端的に言えば、配列の先頭から順に、隣り合う二つの要素の比較をする並べ替えの手法です。
コードで見る
def bubble_sort(numbers: list[int]) -> list[int]:
# 入力されたリストの長さを取得
len_numbers = len(numbers)
# 1. 比較を始めるインデックスを定めるループ
for i in range(len_numbers)
# 2. 具体的に比較をするインデックスを定めるループ*
for j in range(len_numbers - 1 - i):
# 3-1. 左側の要素が右側の要素よりも大きい場合
if numbers[j] > numbers[j+1]:
# 3-2. 値を入れ替える
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
return numbers
それでは、具体例を見ていきましょう。
具体例
これは何の変哲もない長さが3のリストです。この要素が1, 2, 3と左から右へと昇順になっているように変更します。
nums = [3, 2, 1]
3と2を比較します。
# i = 0
# j = 0
nums = [3, 2, 1]
# ↑ ↑
# j j+1
3 > 2 であるため、ifの条件より nums[0] , nums[1] の値を交換します。
# i = 0
# j = 0
nums = [2, 3, 1]
次に3と１を比較します。
# i = 0
# j = 1
nums = [2, 3, 1]
# ↑ ↑
# j j+1
2 > 1 であるため、ifの条件より nums[1] , nums[2] の値を交換します。
# i = 0
# j = 1
nums = [2, 1, 3]
最初の要素の比較がすべて終わりました。ここで、 nums[-1] が一番大きな値である3になっていることがわかります。
バブルソートは1.（コードを参照）の処理が一回終わると、比較した中で一番大きな値が端に移動するようになります。
このことから、比較する必要がないため、2.のrange内がlen_numbers -1 - i となるのです。
続きを見ていきましょう。
2と1を比較します。
# i = 1
# j = 0
nums = [2, 1, 3]
# ↑ ↑
# j j+1
2 > 1であるため、ifの条件より nums[0] , nums[1] の値を交換します
# i = 1
# j = 0
nums = [1, 2, 3]
これでソートが完了します。
参考
現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門
動画を用いた視覚的な説明をしているため、とてもわかりやすいです。アルゴリズムを体系的に詳しく理解したい方はご購入をおすすめします。セール時だと、元の値段よりかなり安く購入できます。