はじめに
Sorting Algorithms（ソートアルゴリズム）は、データを一定の規則に基づいて並べ替えるアルゴリズムです。ソートは、検索やデータの可視化、アルゴリズムのパフォーマンス向上に不可欠なステップです。
この記事では、Pythonで使用される代表的なソートアルゴリズムを基礎から学びます。さらに、それぞれのアルゴリズムの特徴、計算量、使用例を詳しく解説します。
Sorting Algorithmsの基本
ソートアルゴリズムとは
ソートアルゴリズムは、リストや配列のデータを昇順または降順に並べ替えるプロセスを指します。主な目的は次のとおりです：
- データの検索や処理を効率化する。
- データの整列による可視化や整理を行う。
Pythonでのソートの基本操作
Pythonでは、標準ライブラリを使用してソートを簡単に行えます。
numbers = [5, 2, 9, 1, 5, 6]
# 昇順ソート
sorted_numbers = sorted(numbers)
print(sorted_numbers) # 出力: [1, 2, 5, 5, 6, 9]
# リストオブジェクトのソート
numbers.sort()
print(numbers) # 出力: [1, 2, 5, 5, 6, 9]代表的なSorting Algorithms
Bubble Sort
概要
Bubble Sortは、隣り合う要素を比較して順序が間違っていれば交換するアルゴリズムです。最もシンプルですが、効率は低いです。
アルゴリズムのステップ
- 配列の先頭から隣り合う要素を比較。
- 必要に応じて要素を交換。
- 配列が完全にソートされるまで繰り返す。
Pythonでの実装
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
print(numbers) # 出力: [11, 12, 22, 25, 34, 64, 90]計算量
- 最悪ケース：O(n²)
- 平均ケース：O(n²)
Selection Sort
概要
Selection Sortは、配列内で最小（または最大）の要素を選択して適切な位置に移動するアルゴリズムです。
アルゴリズムのステップ
- 配列から最小値を見つける。
- 最小値を先頭に移動。
- 残りの配列で同じ操作を繰り返す。
Pythonでの実装
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
numbers = [64, 25, 12, 22, 11]
selection_sort(numbers)
print(numbers) # 出力: [11, 12, 22, 25, 64]計算量
- 最悪ケース：O(n²)
- 平均ケース：O(n²)
Insertion Sort
概要
Insertion Sortは、ソート済みの部分に新しい要素を挿入するアルゴリズムです。
アルゴリズムのステップ
- 2つ目の要素からスタート。
- 現在の要素をソート済み部分に挿入。
- 配列全体がソートされるまで繰り返す。
Pythonでの実装
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
numbers = [12, 11, 13, 5, 6]
insertion_sort(numbers)
print(numbers) # 出力: [5, 6, 11, 12, 13]計算量
- 最悪ケース：O(n²)
- 平均ケース：O(n²)
Merge Sort
概要
Merge Sortは、分割統治法を利用して配列を小さな部分に分割し、それらを統合してソートするアルゴリズムです。
アルゴリズムのステップ
- 配列を2つに分割。
- 各部分を再帰的にソート。
- 分割された部分を統合。
Pythonでの実装
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
numbers = [12, 11, 13, 5, 6, 7]
merge_sort(numbers)
print(numbers) # 出力: [5, 6, 7, 11, 12, 13]計算量
- 最悪ケース：O(n log n)
- 平均ケース：O(n log n)
ソートアルゴリズムの比較
| アルゴリズム | 最悪計算量 | 平均計算量 | 特徴 |
|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | 簡単だが効率が低い |
| Selection Sort | O(n²) | O(n²) | メモリ効率が良い |
| Insertion Sort | O(n²) | O(n²) | 小規模データに適している |
| Merge Sort | O(n log n) | O(n log n) | 大規模データに適している |
まとめ
ソートアルゴリズムは、データを整理するための基本的な技術です。Pythonでは、標準ライブラリを使った簡単なソートから、アルゴリズムを手動で実装して仕組みを学ぶことができます。
- 小規模データには、簡単なアルゴリズム（Bubble Sort, Insertion Sort）が適しています。
- 大規模データには、効率の良いアルゴリズム（Merge Sort）が適しています。
本記事で紹介した内容を参考に、さまざまなソートアルゴリズムをPythonで試してみてください！