import random
import time
import matplotlib.pyplot as plt

# 1. 基本版バブルソート
def bubble_sort_basic(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 2. フラグ付きバブルソート
def bubble_sort_flag(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(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

# 3. 最後の交換位置を利用するバブルソート
def bubble_sort_last_swap(arr):
    n = len(arr)
    while n > 1:
        last_swap = 0
        for i in range(1, n):
            if arr[i-1] > arr[i]:
                arr[i-1], arr[i] = arr[i], arr[i-1]
                last_swap = i
        n = last_swap

# 4. 双方向バブルソート（シェーカーソート）
def cocktail_sort(arr):
    n = len(arr)
    start, end = 0, n - 1
    while start < end:
        swapped = False
        for i in range(start, end):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swapped = True
        end -= 1
        for i in range(end, start, -1):
            if arr[i-1] > arr[i]:
                arr[i-1], arr[i] = arr[i], arr[i-1]
                swapped = True
        start += 1
        if not swapped:
            break

# 5. Comb Sort
def comb_sort(arr):
    n = len(arr)
    gap = n
    shrink = 1.3
    swapped = True
    while gap > 1 or swapped:
        gap = int(gap / shrink)
        if gap < 1:
            gap = 1
        swapped = False
        for i in range(n - gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True

def merge_sort(arr, depth=0):
    indent = "  " * depth
#    print(f"{indent}MergeSort called on {arr}")
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid], depth + 1)
    right = merge_sort(arr[mid:], depth + 1)
    merged = merge(left, right)
#    print(f"{indent}Merged {left} and {right} into {merged}")
    return merged

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

def quick_sort(arr, depth=0):
    indent = "  " * depth
#    print(f"{indent}QuickSort called on {arr}")
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
#    print(f"{indent}Pivot: {pivot}, Less: {less}, Greater: {greater}")
    sorted_less = quick_sort(less, depth + 1)
    sorted_greater = quick_sort(greater, depth + 1)
    combined = sorted_less + [pivot] + sorted_greater
#    print(f"{indent}Combined into {combined}")
    return combined


def many_pivot_quick_sort(arr, threshold, sample_size):
    if len(arr) <= 1:
        return arr
    if len(arr) >= threshold:
        sample = random.sample(arr, min(sample_size, len(arr)))
        sample.sort()
        pivot = sample[len(sample) // 2]
    else:
        pivot = arr[0]

    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]

    return many_pivot_quick_sort(less, threshold, sample_size) + equal + many_pivot_quick_sort(greater, threshold, sample_size)



# 実行時間を計測する関数
def measure_time(sort_func, data):
    arr = data.copy()
    start = time.perf_counter()
    sort_func(arr)
    end = time.perf_counter()
    return end - start


# 実験設定
sizes = [100, 200, 400, 800, 1600, 3000, 6000, 12000]
algorithms = [
    ("Quick Sort (python)", quick_sort),
    ("Tim Sort (list.sort())", lambda arr: arr.sort()),
    ("Many pivot qs (1000, 127)", lambda arr: many_pivot_quick_sort(arr, 200, 127)),
    ("Merge Sort", merge_sort),
    ("Bubble Basic", bubble_sort_basic),
    ("Bubble Flag", bubble_sort_flag),
    ("Bubble LastSwap", bubble_sort_last_swap),
    ("Cocktail", cocktail_sort),
    ("Comb", comb_sort)
]

results = {name: [] for name, _ in algorithms}

# 実行時間を計測
for n in sizes:
    data = [random.randint(0, 10000) for _ in range(n)]
    for name, func in algorithms:
        t = measure_time(func, data)
        results[name].append(t)

# プロット
plt.figure(figsize=(8,5))
for name in results:
    plt.plot(sizes, results[name], marker='o', label=name)
plt.xlabel("Array size (n)")
plt.ylabel("Time (seconds)")
plt.yscale('log')
plt.title("Sorting Algorithm Performance Comparison")
plt.legend()
plt.grid(True)
plt.show()