정렬의 수학: 왜 O(n log n)이 한계인가

def bubble_sort(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  # 이미 정렬됨
    return arr


print(bubble_sort([5, 3, 1, 4, 2]))  # [1, 2, 3, 4, 5]
# 비교 횟수: n + (n-1) + ... + 1 = n(n+1)/2 ≈ n²/2

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):
    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


print(merge_sort([5, 3, 1, 4, 2]))


# 분석:
# 분할: log n 단계 (절반씩)
# 각 단계 머지: O(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)


print(quick_sort([5, 3, 1, 4, 2]))


# 분석:
# 균등 분할 시: O(n log n)
# 최악(이미 정렬, 끝 피벗): O(n²)
# 무작위 피벗으로 최악 회피

n개 원소의 가능한 순열: n!
각 비교는 1비트 (둘 중 어느 게 큰가) 정보 제공

n!개 결과를 구분하려면 log₂(n!)개 비교 필요
log₂(n!) ≈ n log n - 1.44n (스털링 근사)

→ 비교 정렬은 O(n log n)이 이론적 하한
→ 머지/퀵/힙 정렬이 점근적으로 최적

def counting_sort(arr, max_val):
    """비교 없이 정렬 — O(n + k)"""
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1

    result = []
    for i, c in enumerate(count):
        result.extend([i] * c)
    return result


# 학생 점수 (0~100)
scores = [85, 90, 75, 60, 95, 80, 90, 75]
print(counting_sort(scores, 100))
# [60, 75, 75, 80, 85, 90, 90, 95]


# 조건:
# - 입력값이 정수 (또는 정수로 매핑 가능)
# - 값의 범위 k가 합리적 (k가 너무 크면 메모리 폭주)

# Python sorted() / list.sort()는 Timsort
# 머지 + 삽입 정렬 하이브리드
# 부분 정렬된 데이터에 매우 강함

import random
import time

# 무작위 데이터 — O(n log n)
arr1 = random.sample(range(1_000_000), 100_000)
t0 = time.perf_counter()
sorted(arr1)
print(f"무작위: {(time.perf_counter() - t0)*1000:.0f}ms")


# 거의 정렬됨 — O(n)에 가까움 (Timsort의 강점)
arr2 = list(range(100_000))
random.shuffle(arr2[-100:])  # 끝 100개만 셔플
t0 = time.perf_counter()
sorted(arr2)
print(f"거의 정렬: {(time.perf_counter() - t0)*1000:.0f}ms")


# 이미 정렬됨 — O(n)
arr3 = list(range(100_000))
t0 = time.perf_counter()
sorted(arr3)
print(f"이미 정렬: {(time.perf_counter() - t0)*1000:.0f}ms")

# 같은 키의 원본 순서 보존

students = [
    ('Alice',   90),
    ('Bob',     85),
    ('Charlie', 90),  # Alice와 같은 점수
    ('Dave',    85),  # Bob과 같은 점수
]

# 점수로 정렬 — 안정적이면 같은 점수는 원본 순서
sorted_stable = sorted(students, key=lambda x: x[1], reverse=True)
print(sorted_stable)
# [('Alice', 90), ('Charlie', 90), ('Bob', 85), ('Dave', 85)]
# Alice > Charlie 순서 유지 (원본대로)


# 다중 키 정렬 — 안정 정렬 활용
# "이름 → 점수" 우선순위
sorted_multi = sorted(
    sorted(students, key=lambda x: x[0]),  # 1차: 이름
    key=lambda x: x[1], reverse=True       # 2차: 점수 (안정)
)