バブルソートと挿入ソート
2つの二次時間ソートアルゴリズムを実装し、O(n²)である理由と、挿入ソートがマージソートに勝る一つのケースを理解します。
「バブルソートと挿入ソート」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
O(n²)のソートを学ぶ理由
バブルソートと挿入ソートは最悪の場合O(n²)であるため、大きな入力には実用的ではありません。それでも、本格的なアルゴリズム面接では、これらを実装して分析できることが必ず期待されます。比較、交換、安定ソート、最良ケースの挙動といった基本概念を学べるためです。これらの概念は、より高度なアルゴリズムにも適用できます。面接官は、ループ不変条件や漸近記法について、原理から考えられるかどうかを確認するために、これらのアルゴリズムを使います。
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')バブルソート：最大値を浮上させる
バブルソートは、配列を繰り返し走査し、順序が逆になっている隣接要素を交換します。各パスが終わると、未ソート部分の最大要素が「浮上」して末尾の最終位置に移動します。n-1回のパスで配列全体がソートされます。大きな要素が泡のように上へ浮かぶ様子から、この名前が付いています。説明するのが最も簡単なソートアルゴリズムですが、実際に使われることはほとんどありません。
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]早期終了付きバブルソート
最適化したバブルソートでは、swappedフラグを使います。内側のループを1回実行して交換が1回も発生しなければ、配列はすでにソート済みなので、そこで早期終了します。これにより、すでにソートされた入力に対する最良ケースがO(n)になります。バブルソートにおける唯一の本当の利点です。このフラグがなければ、常にO(n²)回の比較を行います。バブルソートの改善について尋ねられたとき、面接官が確認するのがこの早期終了の最適化です。
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
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: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passバブルソートの計算量分析
バブルソートの外側のループはn-1回実行されます。内側のループは各パスでn-1-i回実行されます。(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2回の比較となります。これにより、平均ケースと最悪ケースはO(n²)です。早期終了フラグを使うと、ソート済みの入力に対する最良ケースはO(n)まで下がります。空間計算量はO(1)です。交換には一時変数が必要なだけです。バブルソートは安定です。等しい要素は相対的な順序を維持します。厳密に大きい要素同士の場合にのみ交換するためです。
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5挿入ソート：整列済みの手札を作る
挿入ソートは、トランプの手札を整理する方法をまねたアルゴリズムです。次のカード（要素）を取り、左側にあるすでに整列済みのカードの中の正しい位置に挿入します。不変条件は、arr[0:i]が常にソート済みであることです。新しい要素ごとに、大きい要素を右へ移動して空きを作ります。このインプレースで安定なアルゴリズムは、最悪ケースがO(n²)ですが、ほぼ整列済みのデータでは最良ケースがO(n)です。
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]挿入ソートを手順ごとに追う
[3, 1, 4, 2]に挿入ソートを適用します。i=1、key=1では、3を右へ移動 → [1, 3, 4, 2]となります。i=2、key=4では、移動はなく、配列は変わりません。i=3、key=2では、4、続いて3を右へ移動 → [1, 2, 3, 4]となります。各要素は、正しい位置が見つかるまで左側の要素と比較されます。内側のwhileループは代入を使って要素を移動します。交換では1回につき3回の代入が必要なのに対し、移動1回につき1回の代入で済むため、交換より高速です。
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]ほぼ整列済みデータでの挿入ソート
挿入ソートの決定的な長所は、O(n + 転倒数)の計算量です。転倒とは、i < jであるにもかかわらずarr[i] > arr[j]となる組(i,j)です。転倒が少ないほぼ整列済みの配列では、挿入ソートは非常に高速です。単純でキャッシュ効率のよいアクセスパターンを持つため、実際にはマージソートより速いことさえあります。PythonのTimsortが小さな部分配列に挿入ソートを使うのは、まさにこの理由です。
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)ソートにおける安定性
ソート後も等しい要素が元の相対的な順序を維持する場合、そのソートアルゴリズムは安定です。バブルソートと挿入ソートはどちらも安定しています。等しい要素を交換しないためです。安定性は、複数のキーで順番にソートするときに重要です。まず副キーで安定ソートし、次に主キーで安定ソートすると、同順位の要素間で副キーの順序を維持できます。マージソートも安定していますが、ヒープソートとクイックソートは一般に安定していません。
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stable二分探索を使う挿入ソート
挿入ソートの内側のループは、正しい位置を見つける処理と要素を移動する処理の両方を行います。二分探索を使えば、O(log i)回の比較で位置を見つけられますが、移動には依然としてO(i)時間かかるため、全体の計算量はO(n²)のままです。この最適化で比較回数は減ります（比較関数のコストが高い場合に有効です）が、操作の総数は減りません。この「二分挿入ソート」は、Timsortで小さなチャンクサイズに対して使われています。
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]バブルソートと挿入ソート：使い分け
面接では、次の比較を自信を持って述べてください。挿入ソートはバブルソートより明確に優れています
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]転倒数を指標として数える
配列内の転倒数は、i < jであるにもかかわらずarr[i] > arr[j]となる組(i,j)の数です。挿入ソートが行う移動回数は、転倒数と正確に一致します。これは重要な洞察です。転倒数を効率よく数える（O(n log n)）には、改良版のマージソートが必要です。面接では、ソートに関する話題の追加質問として、「あなたのアルゴリズムは転倒をどの程度考慮していますか」と尋ねられることがあります。
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs inverted確認問題
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、バブルソートはn-1回のパスを行い、各パスでその時点の最大値を最終位置まで浮上させます。最悪ケースはO(n²)ですが、早期終了フラグがあれば最良ケースはO(n)です、挿入ソートは要素を右にずらして現在のkeyを正しい整列位置に挿入し、O(n + 転倒数)時間で動作するため、ほぼ整列済みデータに最適です、そして両アルゴリズムは安定で、空間計算量はO(1)、最悪ケースはO(n²)ですが、実用上のあらゆる場面で挿入ソートがバブルソートより明確に優先されますということを学びました。次はマージソートをゼロから実装します。
よくある質問
「バブルソートと挿入ソート」レッスンは無料ですか？
はい。「バブルソートと挿入ソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「バブルソートと挿入ソート」で何を学びますか？
2つの二次時間ソートアルゴリズムを実装し、O(n²)である理由と、挿入ソートがマージソートに勝る一つのケースを理解します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「バブルソートと挿入ソート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。