Overview

ソートアルゴリズムの基本を知るため、バブルソートについてまとめました。
1.バブルソートの基本
 2.バブルソートの改良
 3.バブルソートの特徴
 4.典型問題を解いてみる

1. バブルソートの基本

隣接する要素を比較して順序を入れ替えることでリストを並び替える。

＜アルゴリズムの流れ＞
1.リストを左から順に見ていき、隣接する要素を比較。
2.大きい方を後ろに移動（昇順の場合）。
3.リスト全体を繰り返し、最後まで比較が不要になるまで実行。
4.途中で交換が行われなかった場合、ソート済みなので終了。

＜基本実装＞

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):  # 末尾の要素は確定するため、比較回数を減らす
            if arr[j] > arr[j + 1]:  # 昇順ソート
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

実行例

arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr))  # 出力: [2, 3, 4, 5, 8]

2. バブルソートの改良

最適化1：途中で交換が発生しなかったらソート済みなので、ループを途中で抜ける。
最適化2：最も大きい値が右に移動するため、毎回走査範囲を狭める。

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # 交換がなければソート完了
    return arr

3. バブルソートの特徴

時間計算量 : 最悪・平均: $O(N^2)$,最良: $O(N)$(すでにソート済みの場合）
空間計算量 : $O(1)$ (追加メモリ不要）
安定ソート : Yes（元の順序を保持する）
適用場面 : 小規模なデータ、学習目的

4. 典型問題を解いてみる

例題1. バブルソートの基本実装

問題: N 個の整数が与えられる。それらをバブルソートで昇順に並べ替えよ。

参考： ABC333 B - Basic Bubble Sort

回答　

N = int(input())
A = list(map(int, input().split()))

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(*bubble_sort(A))

例題2. バブルソートの交換回数

問題: N 個の整数が与えられる。それらをバブルソートで並べ替える際の「交換回数」を出力せよ。

参考： ABC314 C - Count Swaps

回答　

N = int(input())
A = list(map(int, input().split()))

def bubble_sort_count_swaps(arr):
    n = len(arr)
    swap_count = 0
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swap_count += 1
    return swap_count

print(bubble_sort_count_swaps(A))

例題3. 逆順バブルソート

問題: N 個の整数が与えられる。それらを降順（大きい順）に並べ替えよ。

参考： ABC301 B - Reverse Bubble Sort

回答　

N = int(input())
A = list(map(int, input().split()))

def bubble_sort_desc(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] < arr[j + 1]:  # 昇順の代わりに降順
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(*bubble_sort_desc(A))

例題4. 途中でソートが終了するバブルソート

問題: N 個の整数が与えられる。それらをバブルソートで並べ替える際に、途中で交換が行われなくなった時点で終了するバージョンを実装せよ。

参考： ABC289 B - Early Stop Bubble Sort

回答　

N = int(input())
A = list(map(int, input().split()))

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 交換がなければ終了
            break
    return arr

print(*optimized_bubble_sort(A))

例題5. バブルソートの特定の回数だけ適用

問題: N 個の整数が与えられ、バブルソートを K 回だけ適用した時点の配列を出力せよ。

参考： ABC315 D - Partial Bubble Sort

回答　

N, K = map(int, input().split())
A = list(map(int, input().split()))

def partial_bubble_sort(arr, k):
    n = len(arr)
    for i in range(min(k, n)):  # 最大K回までループ
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(*partial_bubble_sort(A, K))