📚 지식 노트

버블 정렬: 이웃끼리 바꾸기

정렬(sorting)은 값을 정해진 순서로 다시 늘어놓는 일이다. 정렬해 두면 이진 탐색으로 빨리 찾고, 같은 값을 이웃에 모으고, 두 목록을 한 번에 훑어 합칠 수 있다. 그래서 거의 모든 프로그램의 어딘가에서 정렬이 돈다.

가장 단순한 방법이 버블 정렬(bubble sort)이다. 왼쪽부터 이웃한 두 칸을 비교해 순서가 틀리면 바꾼다. 한 바퀴를 돌면 가장 큰 값이 거품처럼 오른쪽 끝까지 떠오르고, 다음 바퀴는 한 칸 짧게 돈다. 한 바퀴 동안 한 번도 바꾸지 않았다면 이미 정렬된 것이니 멈춘다.

• 복잡도: 바퀴가 최대 n-1번, 바퀴마다 비교가 최대 n-1번이라 평균·최악 O(n²)이다. 이미 정렬된 입력은 첫 바퀴에서 멈춰 O(n)이다. 추가 메모리는 O(1)이다.
• 장단점: 같은 값은 바꾸지 않으니 순서가 지켜진다(안정 정렬, 아래 절). 하지만 값 하나가 한 바퀴에 한 칸씩만 왼쪽으로 가서, 같은 O(n²)인 삽입 정렬보다도 대개 느리다.
• 쓰임: 실무 정렬로는 거의 쓰지 않는다. “이웃을 비교해 바꾼다”는 생각이 가장 잘 보여서 처음 배우는 정렬로 남아 있다.

복잡도 표기(빅오)와 최선·평균·최악의 뜻은 기초 노트에 있다. 여러 정렬이 같은 입력을 어떻게 다루는지 나란히 보려면 VisuAlgo의 정렬 시각화가 좋다.

문제 풀기 →Python 코드 →

선택 정렬과 삽입 정렬

둘 다 배열을 “정렬된 왼쪽”과 “남은 오른쪽”으로 나누고 왼쪽을 한 칸씩 늘린다. 차이는 무엇을 먼저 정하느냐다. 선택 정렬(selection sort)은 남은 칸 전체를 훑어 가장 작은 값을 골라 왼쪽 끝에 붙인다. 자리를 먼저 정하고 값을 찾는 셈이다.

삽입 정렬(insertion sort)은 반대로 값을 먼저 정한다. 바로 다음 값 하나를 꺼내, 정렬된 왼쪽에서 그보다 큰 값들을 한 칸씩 밀고 빈자리에 넣는다. 카드 게임에서 손패를 정리하는 방식과 같다.

• 선택 정렬: 입력과 상관없이 비교는 늘 n(n-1)/2번이다. 대신 바꾸기는 많아야 n-1번이라, 쓰기가 비싼 저장 장치처럼 값을 옮기는 비용이 비교보다 훨씬 클 때 의미가 있다. 멀리 있는 칸과 바꾸기 때문에 같은 값의 순서가 뒤집힐 수 있다(불안정).
• 삽입 정렬: 미는 횟수가 “순서가 뒤집힌 쌍”(inversion)의 수와 같다. 이미 정렬된 입력은 O(n), 거꾸로 된 입력은 O(n²)이다. 같은 값은 넘어가지 않으니 안정적이고, 추가 메모리가 필요 없고, 값이 하나씩 들어오는 대로 정렬할 수도 있다(온라인).
• 쓰임: 원소가 수십 개 이하이면 상수가 작은 삽입 정렬이 O(n log n) 정렬보다 빠르다. 그래서 실무 정렬은 작은 조각을 삽입 정렬에 맡긴다. 아래의 Timsort와 인트로 정렬이 그렇다.

문제 풀기 →Python 코드 →

병합 정렬: 나누고 합치기

O(n²)을 벗어나려면 한 번의 비교로 더 많은 것을 알아내야 한다. 병합 정렬(merge sort)은 배열을 반으로 나눠 각각 정렬한 뒤 합친다. 나누기를 되풀이하면 결국 한 칸짜리 조각이 남고, 한 칸은 그 자체로 정렬돼 있다. 어려운 일은 합치기에 있다.

정렬된 두 조각을 합칠 때는 두 조각의 맨 앞만 비교하면 된다. 더 작은 쪽을 꺼내 결과에 붙이고, 꺼낸 조각의 다음 값으로 넘어간다. 비교 한 번마다 값 하나가 확정되니 합치기는 두 조각 길이의 합에 비례한다.

merge_sort(a):
  if len(a) <= 1: return a
  left  = merge_sort(a[:mid])
  right = merge_sort(a[mid:])
  return merge(left, right)   # 앞쪽끼리 비교, 같으면 left 먼저

• 복잡도: 줄마다 합치는 일의 합이 n이고 줄은 log₂ n개라 최선·평균·최악 모두 O(n log n)이다. 입력이 어떻든 느려지지 않는다.
• 대가: 배열을 합칠 때 결과를 담을 O(n) 크기의 임시 공간이 필요하다. 연결 리스트는 포인터만 바꿔 이으면 되니 추가 공간 없이 병합 정렬할 수 있다.
• 쓰임: 같은 값이면 왼쪽 조각을 먼저 꺼내 안정적이다. 메모리에 다 들어가지 않는 큰 파일은 덩어리별로 정렬해 디스크에 쓴 뒤 여러 덩어리를 한꺼번에 합치는데(외부 정렬), 이것도 병합이다.

실무의 대표는 Timsort다. 입력에서 이미 정렬된 구간(run)을 찾아 짧으면 삽입 정렬로 늘리고, run끼리 병합한다. 실제 데이터에는 부분적으로 정렬된 곳이 많아서 이 방식이 잘 맞는다. Python의 정렬, Java의 객체 배열 정렬, V8 엔진의 Array.prototype.sort가 이 계열이다.

문제 풀기 →Python 코드 →

퀵 정렬: 피벗으로 가르기

퀵 정렬(quicksort)은 병합 정렬과 순서가 반대다. 먼저 값 하나를 기준(피벗, pivot)으로 골라 배열을 “피벗보다 작은 쪽”과 “크거나 같은 쪽”으로 가른다(분할, partition). 그러면 피벗은 정렬이 끝났을 때의 자리에 이미 서 있고, 양쪽을 따로 정렬하면 끝이다. 합치는 단계가 없다.

그림은 가장 짧게 쓸 수 있는 로무토(Lomuto) 분할이다. 구간 끝 값을 피벗으로 삼고, j가 왼쪽부터 훑으며 피벗보다 작은 값을 i 칸으로 보낸다. 다 훑으면 i 칸이 피벗의 자리다. 원래 호어(Hoare)가 낸 방식은 양 끝에서 안쪽으로 다가오며 바꾸는데, 바꾸기가 더 적어 실무에서 더 흔하다.

평균은 O(n log n)이다. 피벗이 구간을 대략 반으로 가르면 재귀 깊이가 log n이고, 깊이마다 훑는 양이 n이기 때문이다. 문제는 피벗이 매번 가장 작거나 가장 큰 값일 때다. 맨 끝 값을 피벗으로 쓰는데 입력이 이미 정렬돼 있으면 분할할 때마다 한 칸만 줄어 깊이가 n이 되고, 비교가 n²/2번으로 늘어난다.

• 피벗 고르기: 무작위로 고르거나, 처음·가운데·끝 세 값의 중앙값(median-of-three)을 쓴다. 어떤 입력이 와도 최악이 나올 확률이 아주 작아진다.
• 같은 값이 많을 때: 두 갈래 분할은 같은 값이 한쪽으로 몰려 느려진다. 작다·같다·크다 세 갈래로 가르면(3-way partition) 같은 값 묶음은 더 다루지 않는다.
• 최악 막기: 인트로 정렬(introsort)은 퀵 정렬로 시작해 재귀가 약 2 log n보다 깊어지면 힙 정렬로 바꾸고, 작은 구간은 삽입 정렬로 마무리한다. C++ 표준 라이브러리 구현들이 std::sort에 흔히 쓰는 방식이다.
• 장단점: 제자리에서 배열을 앞뒤로 차례로 훑어 캐시에 잘 맞고 상수가 작아 평균적으로 가장 빠른 축이다. 대신 멀리 있는 칸과 바꾸니 불안정하고, 재귀 스택이 필요하다(작은 쪽부터 재귀하면 O(log n)).
• k번째 값만 필요하면: 분할한 뒤 k번째 자리가 든 한쪽으로만 내려가면 정렬하지 않고도 k번째로 작은 값을 찾는다. 호어가 1961년에 낸 퀵 셀렉트(quickselect)로, 남은 구간이 대략 반씩 줄어 평균 O(n)이고 최악은 퀵 정렬처럼 O(n²)이다. 중앙값이나 상위 몇 %의 값을 구할 때 쓴다.

분할 방식과 피벗 선택, 세 갈래 분할은 Algorithms, 4th Edition의 Quicksort 장에 코드와 실험이 함께 있다. 캐시에 잘 맞는다는 말의 뜻은 CPU 노트의 캐시 부분을 보면 된다.

문제 풀기 →Python 코드 →

힙 정렬: 최댓값을 하나씩 꺼내기

힙 정렬(heap sort)은 배열을 그대로 최대 힙(max-heap)으로 쓴다. 최대 힙은 부모가 언제나 자식보다 크거나 같은 완전 이진 트리이고, 배열의 i번 칸의 자식을 2i+1, 2i+2번 칸으로 보면 포인터 없이 배열 하나로 표현된다. 힙의 자세한 동작은 트리 노트에 있다.

1. 힙 만들기: 자식이 있는 마지막 칸부터 거꾸로 올라가며, 부모가 자식보다 작으면 더 큰 자식과 바꿔 끌어내린다(sift down). 아래쪽 칸일수록 내려갈 거리가 짧아 전체가 O(n)이다.
2. 꺼내기: 맨 위(최댓값)를 힙의 끝 칸과 바꾸면 그 값은 자리가 확정된다. 힙을 한 칸 줄이고, 맨 위로 올라온 값을 끌어내려 다시 힙을 맞춘다. 이걸 n-1번 한다.

• 복잡도: 꺼낼 때마다 트리 높이 log n만큼 내려가니 최악에도 O(n log n)이고, 추가 메모리는 O(1)이다. 이 둘을 동시에 갖춘 비교 정렬은 드물다.
• 단점: i에서 2i+1로 건너뛰는 접근이라 캐시를 잘 못 쓰고, 같은 O(n log n)인 퀵 정렬보다 실제로는 느리다. 멀리 있는 칸과 바꾸니 불안정하다.
• 쓰임: 최악을 보장해야 할 때의 안전망(인트로 정렬), 그리고 전체를 정렬하지 않고 상위 k개만 필요할 때(힙에서 k번만 꺼내기, O(n + k log n))다.

문제 풀기 →Python 코드 →

비교 정렬의 한계와 계수·기수 정렬

지금까지의 정렬은 모두 “두 값 중 어느 쪽이 큰가”만 물어 순서를 알아낸다(비교 정렬, comparison sort). 이런 정렬은 최악에 비교를 약 n log₂ n번보다 적게 할 수 없다. 비교 한 번의 답은 예·아니오 둘 중 하나라서, 질문을 나무처럼 그리면(결정 트리) 잎마다 가능한 순서 하나가 달린다. 가능한 순서는 n!가지이므로 잎이 n!개 이상이어야 하고, 높이가 h인 이진 트리의 잎은 많아야 2^h개다. 그래서 h ≥ log₂(n!)이고, 이 값은 대략 n log₂ n - 1.44n이다.

이 한계를 넘으려면 비교를 하지 않아야 한다. 값이 작은 정수라면 값 자체를 칸 번호로 쓸 수 있다. 계수 정렬(counting sort)은 값마다 몇 개인지 센 뒤, 개수의 누적합으로 각 값이 결과에서 시작할 자리를 구하고, 입력을 앞에서부터 제자리에 옮긴다. 시간과 공간이 O(n + k)이다(k는 값의 범위). 범위 k가 n보다 훨씬 크면 개수 배열이 커져 오히려 손해다.

범위가 큰 정수는 기수 정렬(radix sort)로 자리 숫자마다 나눠 정렬한다. 가장 낮은 자리부터(LSD) 그 자리 숫자로 안정 정렬하기를 자릿수 d번 되풀이하면, 앞 자리에서 맞춘 순서가 뒤 자리의 같은 숫자 안에서 그대로 남아 전체가 정렬된다. 한 번에 O(n + b)(b는 진법, 통의 수)라 전체는 O(d(n + b))다.

• 조건: 키가 정수나 고정 길이 문자열처럼 자리로 쪼갤 수 있어야 한다. 임의의 비교 함수로 정렬하는 범용 정렬은 대신하지 못한다.
• 쓰임: 키가 32비트 정수 같은 고정 폭이면 기수 정렬이 비교 정렬보다 빠를 때가 많다. 병렬로 나누기 쉬워 GPU 정렬에 널리 쓰이고, 문자열은 높은 자리부터 나누는 MSD 방식으로 정렬한다.

자세한 변형과 분석은 Wikipedia의 Radix sort 문서에 정리돼 있다.

문제 풀기 →Python 코드 →

안정성: 같은 값의 순서를 지키는가

키가 같은 두 값이 정렬 뒤에도 입력에서의 순서를 그대로 지키면 그 정렬은 안정적(stable)이다. 숫자만 정렬할 때는 차이가 없지만, 레코드를 키 하나로 정렬할 때는 결과가 달라진다.

• 여러 키로 정렬하기: “학년순, 같은 학년은 이름순”을 원하면 먼저 이름으로 정렬한 뒤 학년으로 안정 정렬하면 된다. 표에서 열 머리를 차례로 눌러 정렬하는 화면이 이렇게 동작한다.
• 안정적인 것: 버블·삽입·병합·계수·기수(LSD), Timsort. 불안정한 것: 선택·퀵·힙. 불안정한 정렬도 원래 위치를 두 번째 키로 덧붙이면 안정적으로 쓸 수 있다.
• 언어별 보장: JavaScript의 Array.prototype.sort는 ES2019부터 안정성이 명세에 들어갔고, Python의 정렬도 안정성을 보장한다. 보장이 없는 언어에서는 문서에 “stable”이 따로 있는지 본다.

문제 풀기 →Python 코드 →

이진 탐색과 lower/upper bound

정렬해 두면 찾기가 빨라진다. 이진 탐색(binary search)은 답이 있을 수 있는 구간의 가운데 값 하나만 보고 절반을 버린다. 원소가 백만 개여도 20번 남짓 보면 끝나니 O(log n)이다.

실무에서는 “이 값이 있나?”보다 “이 값이 들어갈 경계가 어디인가?”를 더 자주 묻는다. lower bound는 target 이상인 첫 칸, upper bound는 target보다 큰 첫 칸이다. 같은 값이 여러 개여도 답이 하나로 정해지고, 두 경계의 차이가 그 값의 개수, lower bound가 정렬을 유지한 채 넣을 자리다.

lower_bound(a, x):
  lo, hi = 0, len(a)          # 답은 늘 [lo, hi) 안에 있다
  while lo < hi:
    mid = lo + (hi - lo) // 2
    if a[mid] < x: lo = mid + 1   # upper bound는 a[mid] <= x
    else: hi = mid
  return lo

• 경계 실수 줄이기: 구간을 반열린 [lo, hi)로 두고 “답은 늘 이 안에 있다”는 불변식을 지키면 +1, -1을 어디에 붙일지 헷갈리지 않는다.
• 넘침: 고정 폭 정수에서 (lo + hi) / 2는 둘을 더하다 넘칠 수 있다. lo + (hi - lo) / 2로 쓴다. 오래 쓰인 표준 라이브러리에서도 실제로 나왔던 버그다.
• 답을 이진 탐색: 배열이 없어도 “x면 가능한가?”가 어느 지점부터 계속 참이면(단조성) 그 경계를 같은 방법으로 찾는다. 최소 용량, 최소 시간 같은 최적화 문제를 이렇게 푼다.
• 쓰임: C++의 std::lower_bound·std::upper_bound, Python의 bisect_left·bisect_right가 바로 이 두 경계다. 데이터베이스 인덱스(B-트리)도 노드 안에서 같은 방식으로 찾는다.

경계 함수의 정확한 약속은 cppreference의 std::lower_bound에, 답을 이진 탐색하는 문제 유형은 cp-algorithms의 Binary search에 있다.

문제 풀기 →Python 코드 →

한눈에 비교

표의 시간은 모두 O(…)이고, k는 값의 범위, d는 자릿수, b는 진법이다. 제자리(in-place)는 배열 밖에 O(1)이나 O(log n) 정도만 더 쓴다는 뜻이다. n이 작을 때는 표의 차수보다 상수가 중요해서 삽입 정렬이 이기고, n이 커지면 차수의 차이가 모든 것을 덮는다.

• 그냥 정렬이 필요하면: 언어의 표준 정렬을 쓴다. 이미 Timsort나 인트로 정렬처럼 위 방법들을 섞어 다듬어 둔 것이다.
• 직접 고를 일이 있다면: 안정성이 필요하면 병합 계열, 메모리를 더 쓸 수 없고 최악을 보장해야 하면 힙, 키가 작은 정수면 계수·기수, 거의 정렬된 입력이 조금씩 바뀌면 삽입 정렬이다.