단순 정렬들: 버블, 선택, 삽입

"다들 버블 정렬을 배우고 그다음 비웃는 법을 배워. 근데 이 '느린' O(n²) 정렬 중 하나가 네가 실제 쓰는 빠른 정렬 안에 조용히 들어있어 — 작거나 거의-정렬된 데이터엔, 단순이 영리함을 이기니까."

세 교육용 정렬

셋 다 O(n²) — 중첩 반복문으로 쌍을 비교 — 인데, 각자 다른 아이디어를 보여줘:

버블 정렬: 순서 어긋난 인접 쌍을 반복 swap; 가장 큰 게 매 패스 끝으로 '거품처럼 올라'. 그리기 제일 단순, 실전에선 거의 맞는 선택 아님 — 주 역할은 다들 만나는 첫 정렬.
선택 정렬: 매 패스가 미정렬 영역의 최솟값을 찾아 배치. swap 수 최소화 (쓰기 비싸면 유용) 지만 늘 O(n²) 비교.
삽입 정렬: 정렬된 접두사를 한 번에 원소 하나씩 지어, 각 새 원소를 제자리에 삽입 — 정확히 대부분 카드 패 정렬하는 방식.

삽입 정렬이 값하는 이유

삽입 정렬이 중요한 거야, 다른 게 없는 진짜 미덕 둘이 있거든. 첫째, 적응적: 이미 정렬됐거나 거의-정렬된 데이터엔, 각 새 원소가 이미 (거의) 제자리라, O(n²) 가 아니라 O(n) 일만 해. 둘째, 작은 상수 오버헤드: 재귀 없음, 추가 메모리 없음, 훌륭한 캐시 행동. 그 조합이 작은 배열에 가장 빠른 정렬로 만들어. 그래서 세계 최고 정렬 — Python 의 Timsort, C++ 의 introsort — 이 큰 데이터를 merge/quick 으로 나누되 바닥의 작은 부분배열엔 삽입 정렬로 전환해. '느린' 정렬이 빠른 것의 부품이야.

버블/선택/삽입 다 O(n²) 인데, 삽입 정렬은 특별해: 적응적 (거의-정렬 데이터에 O(n)) 이고 저-오버헤드라, 작은 배열의 가장 빠른 선택. 그래서 production 정렬이 base case 로 써. '느림' 에도 틈새가 있어; 맹목적으로 무시하지 마.

단순이 맞을 때

판단: 크고 무작위 데이터엔, 절대 이것들에 손대지 마 — 백만 항목에 O(n²) 은 1조 연산. 근데 작은 배열 (가령 ~50 원소 미만), 거의-정렬된 데이터, 또는 코드 단순함이랑 낮은 메모리가 점근보다 중요할 때, 삽입 정렬이 진짜 이길 수 있어. 반복되는 퀘스트 테마 한 번 더: '최고' 알고리즘은 데이터랑 규모에 달렸고, 단순 도구를 통째로 무시하는 게 화려한 걸로 과잉 설계하는 만큼 에러야.

피파의 고백

난 자신만만하게 삽입 정렬이 구식이라고 '알았어' — merge 정렬이 O(n log n) 인데 왜 O(n²) 를 써? 그러다 아빠가 Python 자체 Timsort 가 작은 run 에 삽입 정렬을 부른다고 보여줬어, 작은 배열엔 그 낮은 오버헤드가 merge 정렬의 장부 관리를 이기니까. 난 '더 나쁜 점근 복잡도' 를 '절대 안 유용' 으로 착각했어. 빅오가 버리는 상수가 정확히 삽입 정렬을 작은 규모의 맞는 도구로 만드는 거야 — 점근이 이야기 전부가 아니란 겸손한 상기.

Code

삽입 정렬 — 간직할 가치 있는 그것·python

# 삽입 정렬: 진짜 유용한 단순 정렬. 적응적 + 저-오버헤드.
def insertion_sort(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                  # key 를 그 슬롯에 떨궈
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))   # [1, 2, 3, 4, 5, 6]

# 적응적 승리: 거의-정렬된 데이터엔, 안쪽 while 이 거의 안 돌아.
nearly = [1, 2, 3, 5, 4, 6]    # 원소 하나만 어긋남
# 각 원소가 ~1 단계에 자리 찾음 -> O(n²) 아니라 O(n) 에 가까움.

# 선택 정렬 (swap 최소화) 이랑 버블 정렬 (그리기 제일 단순) 은
# 둘 다 늘 O(n^2) 비교 — 대부분 교육용, 거의 맞는 선택 아님.
# production 정렬 (Timsort) 이 작은 base case 에 *삽입* 정렬을 써.

Exercise

삽입 정렬이 왜 이미 정렬된 배열엔 대략 O(n) 인데 역순 정렬된 거엔 O(n²) 인지 설명해 — 각 경우 안쪽 while-루프가 뭘 하는지 추적해. 그다음 Python Timsort 가 왜 전부 merge-정렬하는 대신 작은 청크에 삽입 정렬을 쓰는 수고를 하는지 설명해.

Hint

정렬된 데이터엔 안쪽 while 이 절대 안 밀어 (각 key 가 이미 선행자 ≥), 그래서 ~n 총 단계. 역순 데이터엔 모든 key 가 끝까지 왼쪽으로 밀려 → ~n²/2. Timsort 가 작은 run 에 삽입 정렬을 쓰는 이유는 작은 크기엔 그 낮은 상수 오버헤드가 merge 정렬의 재귀/할당 비용을 이기니까.

세 교육용 정렬

삽입 정렬이 값하는 이유

단순이 맞을 때

피파의 고백

Code

External links

Exercise

Progress

댓글 0