バブルソート

5.1 バブルソートの定義

バブルソート (Bubble Sort) — これはシンプルなソートアルゴリズムだよ。 リストを何度も通過して隣接する要素を比較して、 間違った順序にある場合はそれらを入れ替えるんだ。このプロセスは、 リストが完全にソートされるまで続けられるよ。

動作の仕組み:

1. アルゴリズムはリストを通過して各隣接要素のペアを比較するよ。
2. もし要素が間違った順序にある場合（昇順では最初の要素が2番目の要素より大きい時）– それらを入れ替えるんだ。
3. このプロセスは、リスト内のすべての要素のペアに対して繰り返されるよ。
4. 各完全な通過の後、最大の要素が自分の場所に「浮かぶ」（水面の泡のように）ので、 次の通過にはもう参加しないんだ。
5. リストがソートされるまで、プロセスは繰り返されるよ。

バブルソートの時間的および空間的な複雑さ

時間的複雑さ:

• 最悪の場合: O(n^2) — 要素が逆順に並んでいる場合に発生するよ。
• 平均の場合: O(n^2) — 要素がランダムに配置される場合に発生するよ。
• 最良の場合: O(n) — 要素がすでにソートされている場合に発生するよ （このケースのために、通過で要素の交換があったかどうかをチェックすることで、 アルゴリズムを最適化できる）。

空間的複雑さ:

O(1) — アルゴリズムが追加のメモリを一定量しか使わないからだよ（ 一時的な値を保存するためのいくつかの変数だけ）。

5.2 アルゴリズムの実装

「バブルソート」アルゴリズムは、リスト/配列の要素をソートするための 最もシンプルで基本的なアルゴリズムだよ。ただ要素をペアで比較して、 必要に応じて入れ替えるだけなんだ。

バージョン 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # 要素の交換

print("ソートされた配列:", array)
# 結果: ソートされた配列: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

内部ループ（緑色で強調表示）は、右隣の要素と要素を比較して、 必要に応じて要素を入れ替えるよ。

バージョン 2:

アルゴリズムにすぐに最適化を追加できるよ：最初の通過の後で 最大の要素は最も右に来るから、次のループではもう考慮する必要がないんだ。

2回目のイテレーション後には、右にはすでに2つの最大の要素があるから、 内部ループをn - 1 ではなくn - 1 - i まで行うことができる。 ここでiは外部ループのイテレーション数だよ。

新しいバージョンはこんな感じになる:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # 要素の交換

print("ソートされた配列:", array)
# 結果: ソートされた配列: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

バージョン 3:

また、配列がすでにほとんどソートされていることもあるよ。 だから、こんな最適化を加えることができる: もし内部ループがすべての要素を通過しても交換が一度も行われなかった場合、 ソートは終わりだよ。

このバージョンでは、交換が最後の通過中に発生したかを追跡する変数swappedが使われてるよ。もし配列を通過した後、一度も交換が発生しなかった場合、それは配列がすでにソートされていることを意味するから、さらなるイテレーションは必要ないんだ。だから、このswapped変数によって、ほとんどソートされた配列でアルゴリズムの動作が大幅に速くなるんだ。

Pythonでのバブルソートの実装:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # 最適化: 交換が発生したかのチェック
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # 要素の交換
                swapped = True
        if not swapped:
            break  # 交換がなければ、配列はすでにソートされている
    return array

# 使用例:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("ソートされた配列:", sorted_array)
# 結果: ソートされた配列: [11, 12, 22, 25, 34, 64, 90]