ソートアルゴリズム

データを特定の順序に並べ替えるアルゴリズム。

バブルソート

隣り合う要素を比較し、必要に応じて交換を繰り返すソートアルゴリズム。

選択ソート

未ソート部分から最小要素を見つけ、先頭に移動させるソートアルゴリズム。

挿入ソート

ソート済み部分に要素を正しい位置に挿入するソートアルゴリズム。

クイックソート

ピボットを基準に分割し、再帰的にソートを行うアルゴリズム。

マージソート

配列を分割し、それぞれをソートしてからマージするアルゴリズム。

安定

同じ値の要素の順序が保持されるソート。

インプレース

追加のメモリを使わず、元のデータ構造内でソートを行う手法。

計算量

アルゴリズムの実行時間を表す指標。

バブルソート

泡が浮き上がる

バブルソートは「泡が浮き上がる」ようなもの。隣り合う要素を比較し、大きい要素を右に移動させます。これを繰り返すことで、大きい要素が右端に「浮き上がり」ます。

なぜバブルソートが必要か？

バブルソートは、最もシンプルなソートアルゴリズムの1つです。理解しやすく、実装も簡単です。ただし、計算量はO(n^2)で、大規模なデータには適していません。

いつ使うか？

小規模なデータをソートする場合
教育目的でアルゴリズムを学ぶ場合
安定なソートが必要な場合

実践テクニック

早期終了を活用する

バブルソートは、1回のパスで交換が発生しなかった場合、早期終了できます。これにより、最悪ケースでもO(n)になります。

安定性を理解する

バブルソートは安定なソートです。同じ値の要素の順序が保持されます。これは、複数のキーを持つオブジェクトをソートする場合に重要です。

1
# バブルソートの実装
2
def bubble_sort(arr):
3
    n = len(arr)
4
    for i in range(n):
5
        for j in range(0, n - i - 1):
6
            if arr[j] > arr[j + 1]:
7
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
8
    return arr
9

10
# 使用例
11
arr = [64, 34, 25, 12, 22, 11, 90]
12
print(bubble_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

選択ソート

最小値を選ぶ

選択ソートは「最小値を選ぶ」ようなもの。未ソート部分から最小要素を見つけ、先頭に移動させます。これを繰り返すことで、配列がソートされます。

なぜ選択ソートが必要か？

選択ソートは、バブルソートよりも効率的な場合があります。特に、書き込み回数が少ないデータに適しています。ただし、計算量はO(n^2)で、大規模なデータには適していません。

いつ使うか？

小規模なデータをソートする場合
書き込み回数を最小化したい場合
メモリ使用量を最小化したい場合

実践テクニック

交換を最小化する

選択ソートは、1回のパスで1つの要素のみを交換します。これは、書き込み回数が多いデータに有効です。

安定性を理解する

選択ソートは安定なソートではありません。同じ値の要素の順序が保持されない可能性があります。これは、複数のキーを持つオブジェクトをソートする場合に注意が必要です。

1
# 選択ソートの実装
2
def selection_sort(arr):
3
    n = len(arr)
4
    for i in range(n):
5
        min_idx = i
6
        for j in range(i + 1, n):
7
            if arr[j] < arr[min_idx]:
8
                min_idx = j
9
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
10
    return arr
11

12
# 使用例
13
arr = [64, 34, 25, 12, 22, 11, 90]
14
print(selection_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

挿入ソート

カードを並べ替える

挿入ソートは「カードを並べ替える」ようなもの。ソート済み部分に要素を正しい位置に挿入します。トランプのカードを手で並べ替えるようなイメージです。

なぜ挿入ソートが必要か？

挿入ソートは、ほぼソート済みのデータに適しています。特に、小規模なデータや、既に部分的にソートされているデータに有効です。平均的な計算量はO(n^2)ですが、最善ケースではO(n)になります。

いつ使うか？

小規模なデータをソートする場合
ほぼソート済みのデータをソートする場合
オンラインでデータをソートする場合

実践テクニック

安定性を活用する

挿入ソートは安定なソートです。同じ値の要素の順序が保持されます。これは、複数のキーを持つオブジェクトをソートする場合に重要です。

バイナリサーチを活用する

挿入ソートでは、挿入位置を見つけるためにバイナリサーチを使うことで、検索を最適化できます。

1
# 挿入ソートの実装
2
def insertion_sort(arr):
3
    for i in range(1, len(arr)):
4
        key = arr[i]
5
        j = i - 1
6
        while j >= 0 and key < arr[j]:
7
            arr[j + 1] = arr[j]
8
            j -= 1
9
        arr[j + 1] = key
10
    return arr
11

12
# 使用例
13
arr = [64, 34, 25, 12, 22, 11, 90]
14
print(insertion_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

クイックソート

分割統治

クイックソートは「分割統治」のようなもの。ピボットを基準に配列を分割し、それぞれを再帰的にソートしてからマージします。これを繰り返すことで、高速にソートできます。

なぜクイックソートが必要か？

クイックソートは、平均的な計算量がO(n log n)の高速なソートアルゴリズムです。大規模なデータに適しています。ただし、最悪ケースではO(n^2)になります。

いつ使うか？

大規模なデータをソートする場合
平均的なパフォーマンスが重要な場合
メモリ使用量が許容できる場合

実践テクニック

ピボットの選択

ピボットの選択は、クイックソートのパフォーマンスに大きく影響します。ランダムなピボットや、中央値を選ぶことで、最悪ケースを回避できます。

安定性を理解する

クイックソートは安定なソートではありません。同じ値の要素の順序が保持されない可能性があります。これは、複数のキーを持つオブジェクトをソートする場合に注意が必要です。

小規模なデータには挿入ソートを使う

クイックソートでは、小規模なデータに対して挿入ソートに切り替えることで、パフォーマンスを向上できます。

1
# クイックソートの実装
2
def quick_sort(arr):
3
    if len(arr) <= 1:
4
        return arr
5
    pivot = arr[len(arr) // 2]
6
    left = [x for x in arr if x < pivot]
7
    middle = [x for x in arr if x == pivot]
8
    right = [x for x in arr if x > pivot]
9
    return quick_sort(left) + middle + quick_sort(right)
10

11
# 使用例
12
arr = [64, 34, 25, 12, 22, 11, 90]
13
print(quick_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

マージソート

分割統治

マージソートは「分割統治」のようなもの。配列を分割し、それぞれをソートしてからマージします。常にO(n log n)の計算量を持ちます。

なぜマージソートが必要か？

マージソートは、常にO(n log n)の計算量を持つ安定なソートアルゴリズムです。大規模なデータに適しています。ただし、追加のメモリが必要です。

いつ使うか？

大規模なデータをソートする場合
安定なソートが必要な場合
一貫したパフォーマンスが必要な場合

実践テクニック

安定性を活用する

マージソートは安定なソートです。同じ値の要素の順序が保持されます。これは、複数のキーを持つオブジェクトをソートする場合に重要です。

インプレース実装を検討する

マージソートは、通常追加のメモリが必要ですが、インプレース実装も可能です。メモリが限られている場合、インプレース実装を検討してください。

1
# マージソートの実装
2
def merge_sort(arr):
3
    if len(arr) <= 1:
4
        return arr
5
    mid = len(arr) // 2
6
    left = merge_sort(arr[:mid])
7
    right = merge_sort(arr[mid:])
8
    return merge(left, right)
9

10
def merge(left, right):
11
    result = []
12
    i = j = 0
13
    while i < len(left) and j < len(right):
14
        if left[i] <= right[j]:
15
            result.append(left[i])
16
            i += 1
17
        else:
18
            result.append(right[j])
19
            j += 1
20
    result.extend(left[i:])
21
    result.extend(right[j:])
22
    return result
23

24
# 使用例
25
arr = [64, 34, 25, 12, 22, 11, 90]
26
print(merge_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

計算量

ソートアルゴリズムの計算量を比較する。

アルゴリズム	平均	最悪	安定	インプレース
バブルソート	O(n^2)	O(n^2)	はい	はい
選択ソート	O(n^2)	O(n^2)	いいえ	はい
挿入ソート	O(n^2)	O(n^2)	はい	はい
クイックソート	O(n log n)	O(n^2)	いいえ	はい
マージソート	O(n log n)	O(n log n)	はい	いいえ

Pythonの組み込みソート

Pythonの組み込みソート関数を確認する。

1
# Pythonの組み込みソート関数
2
arr = [64, 34, 25, 12, 22, 11, 90]
3

4
# sort() メソッド
5
arr_sorted = arr.sort()
6
print(arr_sorted)  # [11, 12, 22, 25, 34, 64, 90]
7

8
# sorted() 関数
9
arr_sorted = sorted(arr)
10
print(arr_sorted)  # [11, 12, 22, 25, 34, 64, 90]

合格ライン

☐ バブルソートを実装できる

☐ 選択ソートを実装できる

☐ 挿入ソートを実装できる

☐ クイックソートを実装できる

☐ マージソートを実装できる

☐ ソートアルゴリズムの計算量を理解している

☐ ソートアルゴリズムの使い分けができる

演習課題

課題1: バブルソートの実装

バブルソートを実装し、配列をソートしてください。

課題2: クイックソートの実装

クイックソートを実装し、配列をソートしてください。

課題3: マージソートの実装

マージソートを実装し、配列をソートしてください。

参考文献

この記事は以下の公的ガイドライン/標準に基づいています。

Sorting HOW TO - 公式ドキュメント
Sorting Algorithm - Wikipedia
Sorting Algorithms in Python - Real Python チュートリアル