삽입 정렬 원리, 파이썬 구현부터 내장 정렬 비교까지

$ python3 - <<'PY'
def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
        print(f"{i}단계: {key} 넣음 → {a}")
    return a
print("결과:", insertion_sort([5, 2, 4, 6, 1, 3]))
PY
1단계: 2 넣음 → [2, 5, 4, 6, 1, 3]
2단계: 4 넣음 → [2, 4, 5, 6, 1, 3]
3단계: 6 넣음 → [2, 4, 5, 6, 1, 3]
4단계: 1 넣음 → [1, 2, 4, 5, 6, 3]
5단계: 3 넣음 → [1, 2, 3, 4, 5, 6]
결과: [1, 2, 3, 4, 5, 6]

$ python3 - <<'PY'
import random
def count(a):
    a = list(a); comps = moves = 0
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0:
            comps += 1
            if a[j] > key:
                a[j + 1] = a[j]; j -= 1; moves += 1
            else:
                break
        a[j + 1] = key
    return comps, moves
n = 1000
random.seed(1)
rnd = [random.random() for _ in range(n)]
nearly = sorted(rnd)
for k in range(0, n, 100):
    nearly[k], nearly[k + 1] = nearly[k + 1], nearly[k]
cases = {"정렬됨": sorted(rnd), "무작위": rnd, "거꾸로": sorted(rnd, reverse=True), "거의 정렬됨": nearly}
for name, data in cases.items():
    c, m = count(data)
    print(f"{name:6} n={n}: 비교 {c:,}번, 이동 {m:,}번")
print("n-1 =", n - 1, "/ n(n-1)/2 =", f"{n * (n - 1) // 2:,}")
PY

$ python3 - <<'PY'
import random, time
def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = key
    return a
def best(f, data, runs=3):
    times = []
    for _ in range(runs):
        t = time.perf_counter(); f(data); times.append(time.perf_counter() - t)
    return min(times)
prev = None
for n in (1000, 2000, 4000, 8000):
    random.seed(n)
    data = [random.random() for _ in range(n)]
    t1 = best(insertion_sort, data)
    t2 = best(insertion_sort, sorted(data))
    ratio = f", 앞의 {n // 2}개보다 {t1 / prev:.1f}배" if prev else ""
    print(f"n={n}: 무작위 {t1:.3f}초{ratio}, 이미 정렬됨 {t2:.4f}초")
    prev = t1
PY
n=1000: 무작위 0.004초, 이미 정렬됨 0.0000초
n=2000: 무작위 0.017초, 앞의 1000개보다 4.4배, 이미 정렬됨 0.0001초
n=4000: 무작위 0.074초, 앞의 2000개보다 4.5배, 이미 정렬됨 0.0001초
n=8000: 무작위 0.300초, 앞의 4000개보다 4.0배, 이미 정렬됨 0.0002초

$ python3 - <<'PY'
def insertion_sort(a, key):
    a = list(a)
    for i in range(1, len(a)):
        item = a[i]; j = i - 1
        while j >= 0 and key(a[j]) > key(item):
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = item
    return a
scores = [("민수", 80), ("지은", 90), ("하나", 80), ("도윤", 70), ("서연", 90)]
print(insertion_sort(scores, key=lambda s: s[1]))
PY
[('도윤', 70), ('민수', 80), ('하나', 80), ('지은', 90), ('서연', 90)]

$ python3 - <<'PY'
import random, time
def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = key
    return a
def best(f, data, runs=3):
    times = []
    for _ in range(runs):
        t = time.perf_counter(); r = f(data); times.append(time.perf_counter() - t)
    return min(times), r
random.seed(8000)
data = [random.random() for _ in range(8000)]
t1, r1 = best(insertion_sort, data)
t2, r2 = best(sorted, data)
print(f"같은 8000개(seed 8000): 삽입 정렬 {t1:.3f}초, sorted() {t2:.4f}초, 약 {t1 / t2:.0f}배 차이, 결과 같음: {r1 == r2}")
PY
같은 8000개(seed 8000): 삽입 정렬 0.306초, sorted() 0.0005초, 약 667배 차이, 결과 같음: True

$ python3 - <<'PY'
import bisect, random
random.seed(1)
data = [random.random() for _ in range(1000)]
result = []
for x in data:
    bisect.insort(result, x)
print("정렬됨:", result == sorted(data), "/ 개수:", len(result))
PY
정렬됨: True / 개수: 1000

$ claude --model opus -p "파이썬으로 리스트를 내림차순으로 정렬하는 삽입 정렬 함수 insertion_sort_desc를 쓰고, 그 아래에 print(insertion_sort_desc([3, 8, 1, 9, 4]))를 넣은 코드만 출력해. sorted()나 sort()는 쓰지 말고, 설명이나 코드 블록 표시는 붙이지 마." > desc.py && cat desc.py && python3 desc.py
def insertion_sort_desc(arr):
    arr = arr[:]
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] < key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


print(insertion_sort_desc([3, 8, 1, 9, 4]))
[9, 8, 4, 3, 1]

$ python3 --version
Python 3.15.0