6강 / 20강

정렬 — 인기순 · 가격순 목록 만들기

같은 결과를 만드는 다섯 가지 방법, 그리고 어마어마한 비용 차이

쇼핑몰 화면에서 손님이 가장 많이 누르는 버튼이 무엇일까요? "낮은 가격순", "인기순", "최신순" — 전부 정렬입니다.

그리고 5강에서 배운 이진 탐색도, 앞으로 배울 순위 집계도 전부 "정렬되어 있다"를 전제로 합니다. 정렬은 알고리즘 세계에서 가장 많이 쓰이는 도구예요.

고등학생같은 결과, 어마어마한 비용 차이

정렬은 답이 하나입니다. 가격순으로 세우면 누가 하든 같은 순서가 나오죠.

답은 같은데 가는 길이 다섯 가지

방법	비용	느낌
버블 · 선택 · 삽입	O(n²)	단순 · 느리다
병합 · 퀵	O(n log n)	복잡 · 빠르다

차이가 얼마나 나나

개수	O(n²)	O(n log n)	배수
100	10,000	664	15배
10,000	1억	13만	750배
100만	1조	2천만	5만 배

커질수록 격차가 벌어진다

비유 — 카드 정리

카드 52장을 순서대로 놓습니다.

버블 정렬 — 옆 사람과 비교해 바꾸기를 계속 반복. 머리는 안 쓰는데 손이 많이 간다
병합 정렬 — 둘로 나눠 각각 정리하고 합친다. 생각은 복잡한데 손이 훨씬 덜 간다

단순한 방법이 힘은 더 든다

고등학생정렬을 배우는 진짜 이유

note 가 짚습니다 — 정렬을 직접 짤 일은 거의 없습니다. 그런데 왜 배울까요?

정렬은 다른 것을 가능하게 만드는 준비 작업이다

정렬해 두면	가능해지는 것
순서대로 배열	이진 탐색 (5강)
같은 것끼리 모임	중복 찾기 — 한 번만 훑으면 된다
큰 것이 앞으로	상위 N개 뽑기 (10강)
기준이 정해짐	페이지 나누기 (7강)

정렬은 목적이 아니라 수단이다

그리고 '분할 정복' 을 배웁니다

병합 정렬의 발상이 알고리즘 전체의 핵심 기술 중 하나예요.

쪼개고 → 각각 풀고 → 합친다

어디에 쓰이나	어떻게
병합 정렬	반으로 나눠 정렬하고 합친다
이진 탐색	반으로 나눠 한쪽만 본다
큰 파일 처리	조각으로 나눠 따로 처리

큰 문제를 작은 같은 문제로 바꾸는 것

이 발상 하나가 O(n²) 를 O(n log n) 으로 바꿉니다. 그게 정렬을 배우는 진짜 이유예요.

느린 정렬 세 가지 — O(n²)

사람이 자연스럽게 떠올리는 방법들은 대부분 O(n²)입니다.

버블 정렬 — 옆 사람과 비교해서 크면 자리를 바꾼다. 계속 반복.
선택 정렬 — 남은 것 중 가장 작은 걸 골라 맨 앞에 놓는다.
삽입 정렬 — 카드 게임처럼, 손에 든 카드를 알맞은 자리에 끼워 넣는다.

8개 정렬에 28번 비교. n이 커지면?

Python 브라우저에서 실행

def 버블정렬(a):
    a = a[:]                       # 원본을 건드리지 않는다
    비교 = 0
    for i in range(len(a)):
        for j in range(len(a) - 1 - i):
            비교 += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a, 비교

가격들 = [39000, 9900, 19000, 45000, 25000, 12000, 7900, 33000]
결과, 비교 = 버블정렬(가격들)
print("정렬 결과:", 결과)
print("비교 횟수:", 비교, "번   (n =", len(가격들), ", n² =", len(가격들)**2, ")")

빠른 정렬 두 가지 — O(n log n)

병합 정렬과 퀵 정렬은 완전히 다른 아이디어를 씁니다. 쪼개서 정복하기(분할 정복)예요.

병합 정렬 — 반으로 쪼개고, 또 쪼개고, 하나가 되면 정렬하면서 합친다. 항상 O(n log n). 안정적.
퀵 정렬 — 기준값(피벗) 하나를 잡고 작은 것은 왼쪽, 큰 것은 오른쪽으로 나눈 뒤 각각 다시 정렬. 보통 가장 빠르지만 최악에는 O(n²).

쪼개고 → 정렬하며 합치기. 이것이 분할 정복입니다.

Python 브라우저에서 실행

def 병합정렬(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    왼 = 병합정렬(a[:mid])          # 반으로 쪼개서
    오 = 병합정렬(a[mid:])          # 각각 정렬한 뒤
    # 정렬된 둘을 '합치면서' 정렬한다
    결과, i, j = [], 0, 0
    while i < len(왼) and j < len(오):
        if 왼[i] <= 오[j]:
            결과.append(왼[i]); i += 1
        else:
            결과.append(오[j]); j += 1
    return 결과 + 왼[i:] + 오[j:]

가격들 = [39000, 9900, 19000, 45000, 25000, 12000, 7900, 33000]
print(병합정렬(가격들))

🎮 정렬 경주

다섯 가지 정렬을 같은 데이터로 돌려 봅시다. 막대가 움직이는 모양이 알고리즘마다 완전히 다릅니다. 개수를 12 → 60으로 늘리면서 비교 횟수가 어떻게 벌어지는지 보세요.

실제 비용 — 상품 3만 개를 정렬하면

알고리즘	복잡도	n = 30,000 일 때 비교 횟수
버블 · 선택 · 삽입	`O(n²)`	약 9억 번 💀
병합 · 퀵 · 파이썬 sorted	`O(n log n)`	약 45만 번

2,000배 차이입니다. 같은 결과를 만드는데요.

3,000개만으로도 이 정도 차이입니다. 30,000개면 100배 더 벌어져요.

Python 브라우저에서 실행

import time, random

데이터 = [random.randint(1, 100000) for _ in range(3000)]

def 삽입정렬(a):
    a = a[:]
    for i in range(1, len(a)):
        키 = a[i]; j = i - 1
        while j >= 0 and a[j] > 키:
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = 키
    return a

t0 = time.time(); 삽입정렬(데이터);        t1 = time.time()
t2 = time.time(); sorted(데이터);          t3 = time.time()

print(f"삽입 정렬  O(n²)      : {(t1-t0)*1000:>8.1f} ms")
print(f"sorted()   O(n log n) : {(t3-t2)*1000:>8.1f} ms")
print(f"→ 약 {(t1-t0)/max(t3-t2, 1e-9):,.0f} 배 차이")

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

note 가 정직하게 말합니다. 직접 짠 정렬은 쓰지 마세요.

파이썬의 sorted() 는 수십 년간 다듬어진 코드다

왜 이길 수 없나

이유	설명
C 로 짜여 있다	파이썬보다 수십 배 빠르다
Timsort	이미 정렬된 부분을 알아본다
수많은 검증	가장자리 경우가 전부 처리됨

두 번째가 특히 영리하다

Timsort 가 뭔가

실제 자료는 완전히 뒤죽박죽이 아닙니다. 이미 일부는 정렬되어 있어요.

Timsort 는 그 부분을 찾아서 그대로 쓰고, 나머지만 정렬합니다.

이미 정렬된 자료면 O(n) 만에 끝난다

비유 — 이미 반쯤 정리된 방

방을 정리하는데 책장은 이미 정리되어 있다면? 책장은 건드리지 않고 나머지만 하면 되죠.

Timsort 가 정확히 그렇게 합니다. 현실의 자료 모양을 노린 설계예요.

이론적으로 최적인 것과 실제로 빠른 것은 다를 수 있다

그럼 왜 직접 짜 봤나

비용 감각을 얻으려고요. sorted() 가 공짜가 아니라는 것을 아는 게 중요합니다.

다음 note 가 그 이야기입니다.

고등학생정렬은 공짜가 아닙니다

이 note 가 실무에서 가장 자주 놓치는 부분입니다.

sorted() 도 O(n log n) 이 든다

흔한 실수

반복문 안에서 정렬하는 것입니다.

코드	비용
정렬 한 번 하고 반복	O(n log n)
반복 안에서 매번 정렬	O(n² log n)

밖으로 빼기만 해도 n 배 빨라진다

비유 — 요리할 때마다 장 보기

재료를 한 번에 사 오는 것과 요리 단계마다 마트에 다시 가는 것.

같은 요리인데 시간이 완전히 다르죠.

반복문 안에 무거운 작업이 있는지 늘 확인하라

그리고 정렬이 필요 없을 때도 있습니다

목적	정렬이 필요한가
전체를 순서대로 보여 준다	필요
상위 10개만 필요하다	불필요 — 10강의 방법
가장 큰 것 하나	불필요 — `max()`

상위 10개를 위해 100만 개를 정렬하는 것은 낭비다

10강에서 전체 정렬 없이 상위 N개를 뽑는 법을 배웁니다. heapq.nlargest() 라는 도구가 있어요.

퀴즈가 이걸 묻습니다 — 한 번만 검색할 거면 정렬하지 말고 그냥 훑는 게 낫습니다.

🤔 확인 문제

상품 30,000개를 버블 정렬로 정렬하면 비교 횟수는 대략?

🤔 확인 문제

병합 정렬과 퀵 정렬이 O(n²)보다 빠른 근본 이유는?

🤔 확인 문제

데이터를 한 번만 검색할 예정입니다. 정렬 후 이진 탐색과 그냥 선형 탐색 중 무엇이 유리할까요?