17강 / 20강

정렬 — 순서를 만드는 여러 가지 방법

같은 결과, 완전히 다른 속도

16강에서 정렬해 두면 찾기가 빨라진다는 걸 배웠습니다. 그럼 정렬은 어떻게 할까요? 방법이 아주 많고, 속도가 하늘과 땅 차이입니다.

카드 7장을 순서대로 놓는다고 상상하면서 읽어 보세요.

이름	발상	비교 횟수
버블 정렬	옆 사람과 비교해 자리 바꾸기를 반복	🐢 n²
선택 정렬	남은 것 중 가장 작은 걸 골라 앞에 놓기	🐢 n²
삽입 정렬	카드를 한 장씩 알맞은 자리에 끼워 넣기	🐢 n² (거의 정렬된 경우 ⚡ n)
병합 정렬	반씩 쪼개서 정렬한 뒤 합치기	⚡ n log n
퀵 정렬	기준보다 작은 것/큰 것으로 가르기	⚡ n log n (평균)

고등학생같은 결과, 완전히 다른 속도

정렬은 결과가 하나입니다. 그런데 방법은 수십 가지고 속도는 하늘과 땅이에요.

같은 답을 내는데 1초와 3시간의 차이가 난다

두 부류로 나뉩니다

부류	속도	예
단순한 것	O(n²)	버블 · 선택 · 삽입
나누는 것	O(n log n)	병합 · 퀵 · 힙

10만 개에서 100억 vs 170만 — 6000배

왜 이렇게 차이 나나

방식	비교하는 방법
O(n²)	모든 쌍을 다 비교한다
O(n log n)	절반씩 나눠서 정복한다

"나누어 정복" 이 log 를 만든다 — 16강의 그 마법

비유 — 카드 정렬하기

방법	비유
선택 정렬	전부 훑어 가장 작은 것을 뽑는다 — 매번
삽입 정렬	손에 든 카드에 제자리를 찾아 끼운다
병합 정렬	둘로 나눠 각자 정렬하고 합친다

사람이 카드를 정리하는 방식은 대개 삽입 정렬이다

가장 단순하고 가장 느린 정렬 — 버블 정렬.

Python 브라우저에서 실행

def 버블정렬(값들):
    ㄱ = 값들[:]
    비교 = 교환 = 0
    for ㅇ in range(len(ㄱ)):
        for ㅈ in range(len(ㄱ) - 1 - ㅇ):
            비교 += 1
            if ㄱ[ㅈ] > ㄱ[ㅈ+1]:
                ㄱ[ㅈ], ㄱ[ㅈ+1] = ㄱ[ㅈ+1], ㄱ[ㅈ]   # 자리 바꾸기
                교환 += 1
    return ㄱ, 비교, 교환

원본 = [5, 2, 9, 1, 7, 3, 8]
결과, 비교, 교환 = 버블정렬(원본)
print("원본:", 원본)
print("정렬:", 결과)
print(f"비교 {비교}번, 교환 {교환}번")

🎮 정렬 애니메이션

다섯 가지 정렬이 막대를 어떻게 움직이는지 눈으로 보세요. 아래에 비교 횟수가 실시간으로 세어집니다. 개수를 늘려서 격차를 확인해 보세요.

고등학생병합 정렬 — 재귀가 빛나는 곳

note 가 말하듯 9강의 재귀가 여기서 빛납니다.

반으로 쪼개 각각 정렬하고 → 정렬된 둘을 합친다

세 줄로 끝납니다

def 병합정렬(x):
    if len(x) <= 1: return x
    반 = len(x) // 2
    return 합치기(병합정렬(x[:반]), 병합정렬(x[반:]))

9강의 그 방식 — 믿고 맡긴다

"왼쪽 반이 어떻게 정렬되는지" 는 생각하지 않습니다. 이미 정렬됐다고 가정하고 합치기만 하죠.

합치기가 왜 빠른가

둘 다 정렬돼 있으면 맨 앞만 비교하면 됩니다.

왼쪽	오른쪽	고르는 것
[1, 5, 9]	[3, 7]	1
[5, 9]	[3, 7]	3
[5, 9]	[7]	5

n개를 합치는 데 n번 비교 — 전체를 다시 볼 필요가 없다

왜 n log n 인가

단계	일의 양
쪼개는 깊이	log n 층
각 층에서 합치기	n 번
전체	n × log n

층마다 n번씩, 층이 log n개 — 곱하면 n log n

비유 — 조별 과제

40명이 자료를 정리합니다.

방법	시간
한 명이 전부	오래
2명씩 나눠 하고 합친다	훨씬 빠르다

나누어 맡기고 합치는 비용이 싸면 이긴다

한 회차마다 어떻게 바뀌는지 출력해 봅니다.

Python 브라우저에서 실행

def 선택정렬(값들):
    ㄱ = 값들[:]
    for ㅇ in range(len(ㄱ)):
        최소 = ㅇ
        for ㅈ in range(ㅇ + 1, len(ㄱ)):
            if ㄱ[ㅈ] < ㄱ[최소]:
                최소 = ㅈ
        ㄱ[ㅇ], ㄱ[최소] = ㄱ[최소], ㄱ[ㅇ]
        print(f"  {ㅇ+1}회차: {ㄱ}   ← 앞의 {ㅇ+1}개는 확정")
    return ㄱ

print("선택 정렬 — 가장 작은 걸 골라 앞으로")
선택정렬([5, 2, 9, 1, 7])

def 삽입정렬(값들):
    ㄱ = 값들[:]
    for ㅇ in range(1, len(ㄱ)):
        카드 = ㄱ[ㅇ]
        ㅈ = ㅇ - 1
        while ㅈ >= 0 and ㄱ[ㅈ] > 카드:
            ㄱ[ㅈ+1] = ㄱ[ㅈ]        # 자리를 만들기 위해 밀어낸다
            ㅈ -= 1
        ㄱ[ㅈ+1] = 카드
        print(f"  {ㅇ}회차: {ㄱ}")
    return ㄱ

print()
print("삽입 정렬 — 손에 든 카드를 알맞은 자리에 끼워 넣기")
삽입정렬([5, 2, 9, 1, 7])

병합 정렬 — 쪼개고, 정렬하고, 합친다

9강의 재귀가 여기서 빛납니다. 반으로 쪼개서 각각 정렬한 뒤, 정렬된 둘을 합치기. "각각 정렬"은 같은 문제니까 자기 자신을 부르면 되죠.

합치는 일은 쉽습니다 — 양쪽 맨 앞을 비교해 작은 걸 가져오면 되니까요.

고등학생안정 정렬이 왜 중요한가

잘 언급되지 않지만 실무에서 중요한 성질입니다.

안정 정렬 = 값이 같으면 원래 순서를 유지한다

왜 중요한가 — 두 번 정렬할 때

학생을 반 → 이름 순으로 정렬하려면?

순서	하는 일
1	이름으로 정렬
2	반으로 정렬

안정 정렬이면 같은 반 안에서 이름순이 유지된다

불안정 정렬이면 2번에서 이름 순서가 흐트러집니다.

비유 — 서류 정리

서류를 날짜순으로 정리해 놓고 부서별로 다시 나눕니다.

정리 방식	결과
순서를 지키며 나눈다	부서 안에서 날짜순 ✔
막 섞어 나눈다	날짜 순서가 깨진다 ⚠

한 번에 하나씩 정렬해도 여러 기준이 쌓인다

어느 것이 안정인가

정렬	안정
병합 정렬	✔
삽입 정렬	✔
퀵 정렬	✗
힙 정렬	✗
파이썬 sorted()	✔

파이썬은 안정 정렬을 보장한다 — 믿고 쓸 수 있다

한 번에 여러 기준으로 정렬하기

sorted(학생들, key=lambda s: (s["반"], s["이름"]))

4강의 튜플이 여기서 쓰인다 — 앞에서부터 비교

쪼개지고 합쳐지는 과정을 들여쓰기로 봅니다.

Python 브라우저에서 실행

def 병합정렬(값들, 깊이=0):
    if len(값들) <= 1:
        return 값들
    가운데 = len(값들) // 2
    print("  " * 깊이 + f"쪼갬 {값들} → {값들[:가운데]} / {값들[가운데:]}")
    왼 = 병합정렬(값들[:가운데], 깊이 + 1)
    오 = 병합정렬(값들[가운데:], 깊이 + 1)

    합침, ㅇ, ㅈ = [], 0, 0
    while ㅇ < len(왼) and ㅈ < len(오):
        if 왼[ㅇ] <= 오[ㅈ]:
            합침.append(왼[ㅇ]); ㅇ += 1
        else:
            합침.append(오[ㅈ]); ㅈ += 1
    합침 += 왼[ㅇ:] + 오[ㅈ:]
    print("  " * 깊이 + f"합침 {왼} + {오} → {합침}")
    return 합침

print("결과:", 병합정렬([5, 2, 9, 1, 7, 3]))

직접 재 보세요. 개수를 2배로 할 때 시간이 몇 배가 되는지가 핵심입니다.

Python 브라우저에서 실행

import random, time

def 버블정렬(ㄱ):
    ㄱ = ㄱ[:]
    for ㅇ in range(len(ㄱ)):
        for ㅈ in range(len(ㄱ)-1-ㅇ):
            if ㄱ[ㅈ] > ㄱ[ㅈ+1]:
                ㄱ[ㅈ], ㄱ[ㅈ+1] = ㄱ[ㅈ+1], ㄱ[ㅈ]
    return ㄱ

for ㄴ in [200, 400, 800, 1600]:
    자료 = [random.randint(0, 9999) for _ in range(ㄴ)]

    시작 = time.time(); 버블정렬(자료); 버블 = time.time() - 시작
    시작 = time.time(); sorted(자료);   파이썬 = time.time() - 시작

    print(f"{ㄴ:5}개 → 버블 {버블*1000:8.1f} ms | sorted() {파이썬*1000:6.2f} ms"
          f" | {버블/max(파이썬,1e-9):7.0f}배 차이")

print()
print("개수가 2배가 될 때 버블은 약 4배씩 느려집니다 (n²).")
print("sorted() 는 약 2배씩만 느려집니다 (n log n).")

고등학생실전에서는 sorted() 를 쓰세요

note 의 이 조언은 겸손이 아니라 사실입니다.

파이썬의 정렬은 수십 년간 다듬어진 것이다

Timsort — 파이썬이 쓰는 정렬

특징	설명
이미 정렬된 부분을 찾는다	현실 자료는 부분적으로 정렬돼 있다
작은 조각은 삽입 정렬	작을 땐 그게 더 빠르다
큰 조각은 병합	—
안정하다	—

이미 정렬된 자료면 O(n) 에 끝난다 — 이론 최소치

왜 이게 대단한가

현실 자료는 완전히 무작위가 아닙니다.

흔한 자료	성질
날짜순 기록	거의 정렬됨
정렬 후 몇 개 추가	대부분 정렬됨
여러 정렬본을 합침	덩어리로 정렬됨

Timsort 는 현실 자료에 맞춰 설계됐다 — 그래서 이긴다

그럼 정렬을 왜 배우나

얻는 것	설명
나누어 정복	수많은 알고리즘의 뼈대
n log n 의 감각	19강
안정성 같은 성질	실무에서 쓴다
왜 빠른지	느릴 때 원인을 찾는다

직접 만들지 않아도 고를 수는 있어야 한다

비유 — 요리와 제빵

빵을 직접 굽지 않아도 좋은 빵을 고를 줄은 알아야 합니다.

그러려면 어떻게 만드는지 는 알아야 하죠.

만들 줄 아는 것과 고를 줄 아는 것은 다르고 — 둘 다 필요하다

실전 정렬 — key 로 기준을 정합니다. 튜플을 주면 2순위 기준까지.

Python 브라우저에서 실행

학생 = [
    {"이름": "민준", "점수": 88, "반": 2},
    {"이름": "서연", "점수": 95, "반": 1},
    {"이름": "지호", "점수": 88, "반": 1},
    {"이름": "하윤", "점수": 76, "반": 2},
]

for ㅅ in sorted(학생, key=lambda ㅇ: ㅇ["점수"], reverse=True):
    print(f'{ㅅ["점수"]}점 {ㅅ["이름"]}')

print()
print("반 → 점수(높은 순) 두 기준으로:")
for ㅅ in sorted(학생, key=lambda ㅇ: (ㅇ["반"], -ㅇ["점수"])):
    print(f'{ㅅ["반"]}반 {ㅅ["점수"]}점 {ㅅ["이름"]}')

🤔 확인 문제

버블 정렬에서 값의 개수가 2배가 되면 걸리는 시간은 대략?

🤔 확인 문제

병합 정렬의 핵심 발상은?

🤔 확인 문제

실무에서 정렬이 필요할 때 가장 올바른 선택은?

해설 sorted()는 C로 만들어진 Timsort로, 직접 짠 어떤 파이썬 정렬보다 빠르고 안정적입니다. 알고리즘을 배우는 것과 실무에서 뭘 쓸지는 다른 문제예요.