<一覧に戻る
ソートアルゴリズムの計算量と用途
ソートアルゴリズムは、データを特定の順序（通常は昇順または降順）に並べ替えるための手法です。ここでは、いくつかの主要なソートアルゴリズムの計算量、用途、そしてPythonでの実装例を紹介します。
ソートアルゴリズムの種類
1. バブルソート
バブルソートは、隣接する要素を比較し、順序が正しくない場合は交換することで、リストをソートします。
計算量
- 最悪時: O(n^2)
- 最良時: O(n)（すでにソートされている場合）
- 平均: O(n^2)
用途
小規模なデータセットや教育目的でよく使われますが、大規模なデータには不向きです。
実装
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
# 使用例
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = bubble_sort(data)
print("バブルソート結果:", sorted_data)
2. 挿入ソート
挿入ソートは、リストを部分的にソートしながら、新しい要素を適切な位置に挿入していく手法です。
計算量
- 最悪時: O(n^2)
- 最良時: O(n)（すでにソートされている場合）
- 平均: O(n^2)
用途
小規模なデータセットや、ほぼソート済みのデータに対して効果的です。
実装
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
return arr
# 使用例
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = insertion_sort(data)
print("挿入ソート結果:", sorted_data)
3. 選択ソート
選択ソートは、未ソートの部分から最小（または最大）要素を選択し、ソート済みの部分に追加する手法です。
計算量
- 最悪時: O(n^2)
- 最良時: O(n^2)
- 平均: O(n^2)
用途
小規模なデータセットに対して使用されることが多いですが、効率は悪いです。
実装
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 使用例
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = selection_sort(data)
print("選択ソート結果:", sorted_data)
4. クイックソート
クイックソートは、分割統治法に基づいた効率的なソートアルゴリズムです。基準となるピボットを選び、ピボットを中心に小さい要素と大きい要素に分けて再帰的にソートします。
計算量
- 最悪時: O(n^2)（すでにソートされている場合）
- 最良時: O(n log n)
- 平均: O(n log n)
用途
大規模データのソートに適しています。
実装
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 使用例
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = quick_sort(data)
print("クイックソート結果:", sorted_data)
5. マージソート
マージソートも分割統治法を用いたソートアルゴリズムで、リストを半分に分割し、それぞれをソートした後、マージしていきます。
計算量
- 最悪時: O(n log n)
- 最良時: O(n log n)
- 平均: O(n log n)
用途
安定したソートが必要な場合や、大規模データに適しています。
実装
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
sorted_arr = []
while left and right:
if left[0] < right[0]:
sorted_arr.append(left.pop(0))
else:
sorted_arr.append(right.pop(0))
sorted_arr.extend(left)
sorted_arr.extend(right)
return sorted_arr
# 使用例
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = merge_sort(data)
print("マージソート結果:", sorted_data)
まとめ
ソートアルゴリズムには、それぞれ異なる計算量と用途があります。バブルソートや挿入ソートは小規模なデータに適しており、クイックソートやマージソートは大規模なデータに最適です。実際のアプリケーションでは、データの特性や要件に応じて適切なアルゴリズムを選ぶことが重要です。