ソートアルゴリズム比較！バブルからクイックソートまで初心者にもわかる基礎知識

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]
    
    return arr

# 使用例
numbers = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", numbers)
sorted_numbers = bubble_sort(numbers.copy())
print("ソート後:", sorted_numbers)

def selection_sort(arr):
    n = len(arr)
    
    # 未整列部分の先頭位置を順に移動
    for i in range(n):
        # 未整列部分の最小値を探す
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 最小値を未整列部分の先頭と交換
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

# 使用例
numbers = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", numbers)
sorted_numbers = selection_sort(numbers.copy())
print("ソート後:", sorted_numbers)

def insertion_sort(arr):
    n = len(arr)
    
    # 2番目の要素から順に処理
    for i in range(1, n):
        key = arr[i]  # 挿入する値
        j = i - 1
        
        # keyより大きい要素を右にずらす
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 適切な位置にkeyを挿入
        arr[j + 1] = key
    
    return arr

# 使用例
numbers = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", numbers)
sorted_numbers = insertion_sort(numbers.copy())
print("ソート後:", sorted_numbers)

def merge_sort(arr):
    # 要素が1つ以下なら既にソート済み
    if len(arr) <= 1:
        return arr
    
    # 配列を半分に分割
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # 左半分を再帰的にソート
    right = merge_sort(arr[mid:])   # 右半分を再帰的にソート
    
    # 2つの整列済み配列を結合
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # 両方の配列から小さい方を取り出して結合
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 残りの要素を追加
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 使用例
numbers = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", numbers)
sorted_numbers = merge_sort(numbers)
print("ソート後:", sorted_numbers)

def quick_sort(arr):
    # 要素が1つ以下なら既にソート済み
    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)

# 使用例
numbers = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", numbers)
sorted_numbers = quick_sort(numbers)
print("ソート後:", sorted_numbers)

import time
import random

def measure_sort_time(sort_func, arr):
    """ソート関数の実行時間を計測"""
    start = time.time()
    sort_func(arr.copy())
    end = time.time()
    return end - start

# テストデータの準備
small_data = random.sample(range(1000), 100)      # 100個
medium_data = random.sample(range(10000), 1000)   # 1000個
large_data = random.sample(range(100000), 10000)  # 10000個

# 各アルゴリズムの比較(100個のデータ)
print("=== 100個のデータ ===")
print(f"挿入ソート: {measure_sort_time(insertion_sort, small_data):.6f}秒")
print(f"マージソート: {measure_sort_time(merge_sort, small_data):.6f}秒")
print(f"クイックソート: {measure_sort_time(quick_sort, small_data):.6f}秒")

# 大量データではO(n²)のアルゴリズムは省略
print("\n=== 10000個のデータ ===")
print(f"マージソート: {measure_sort_time(merge_sort, large_data):.6f}秒")
print(f"クイックソート: {measure_sort_time(quick_sort, large_data):.6f}秒")