정렬 알고리즘 — 버블·병합·퀵을 눈으로 비교

정렬 알고리즘을 세 줄로 요약하면:

아래에서 같은 배열 [7, 3, 9, 1, 5, 8, 2, 6]이 각 알고리즘에서 어떻게 정렬되는지 단계별로 보세요. 움직임의 차이가 복잡도의 차이입니다.

버블 정렬 — 이웃한 원소를 반복 교환

버블 정렬은 왼쪽부터 오른쪽으로 훑으면서, 옆에 있는 두 원소의 순서가 틀리면 교환합니다. 한 번 끝까지 가면 가장 큰 값이 맨 뒤로 "떠오릅니다". 이걸 반복.

[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]

한 번에 하나씩만 확정되니까, n개 원소를 정렬하려면 최악 $n \times n$ 번 비교 → $O(n^2)$ .

언제 쓰나? 교육용. 정렬 개념을 처음 배울 때 "교환"이 뭔지 이해하기 좋음. 실제 서비스에서는 절대 안 씀.

병합 정렬의 핵심 아이디어: 이미 정렬된 두 리스트를 합치는 건 쉽다. 그래서 계속 반으로 쪼개서 원소 1개짜리로 만든 뒤, 합치면서 정렬.

[5, 1, 4, 2] \to [5, 1] + [4, 2] \to [1, 5] + [2, 4] \to [1, 2, 4, 5]

매 단계마다 n개를 한 번씩 처리하고, 단계 수는 $\log n$ 번 → $O(n \log n)$ . 항상.

장점: 최악이 없음. 어떤 입력이든 $O(n \log n)$ . 안정 정렬(같은 값의 순서 유지).

단점: 합칠 때 추가 메모리가 필요함.

피벗(기준값) 하나를 고르고, 나머지를 "피벗보다 작은 것 / 큰 것"으로 나눈 뒤, 양쪽을 재귀적으로 정렬.

[5, 1, 4, 2] \xrightarrow{\text{pivot}=4} [1, 2] \;|\; 4 \;|\; [5]

피벗이 데이터를 균등하게 나누면 $O(n \log n)$ . 하지만 매번 최솟값이나 최댓값을 피벗으로 고르면 한쪽이 n-1개가 되어 → 최악 $O(n^2)$ .

그래도 퀵 정렬을 쓰는 이유?

알고리즘	핵심 동작	평균	최악	추가 메모리
버블 정렬	이웃 교환 반복	$O(n^2)$	$O(n^2)$	$O(1)$
병합 정렬	분할 → 합병	$O(n \log n)$	$O(n \log n)$	$O(n)$
퀵 정렬	피벗 분할 → 재귀	$O(n \log n)$	$O(n^2)$	$O(\log n)$

기억법: 버블은 이웃을 바로잡고, 병합은 절반을 합치고, 퀵은 피벗으로 나눈다.

"퀵 정렬이 항상 가장 빠르다" — 아닙니다. 피벗 선택이 나쁘면 $O(n^2)$ 까지 떨어집니다. "보통 가장 빠르다"가 정확한 표현입니다.

" $O(n \log n)$ 인 알고리즘은 다 같다" — 병합과 퀵은 같은 $O(n \log n)$ 이지만, 메모리 사용·안정성·최악 보장이 다릅니다. 빅오가 같다 ≠ 성능이 같다.

"리스트가 작으면 아무거나 써도 된다" — 맞습니다. 실제로 Python의 Timsort는 작은 부분에서 삽입 정렬(= 버블의 업그레이드)을 사용합니다. 실전에서는 혼합 전략이 대부분.

직접 풀어보기

#1쉬움

배열 [7, 3, 9, 1]에 버블 정렬을 적용할 때, 첫 번째 패스(순회) 후 배열 상태를 쓰세요.

#2보통

이미 정렬된 배열 [1, 2, 3, 4, 5]에서 퀵 정렬의 첫 번째 원소를 피벗으로 고르면 어떤 문제가 생기나요? 시간 복잡도는?

Hint

피벗보다 작은 원소가 0개, 큰 원소가 n-1개가 됩니다.

#3어려움

병합 정렬이 항상 O(n log n)인 이유를 분할 단계의 깊이(log n)와 각 단계의 병합 비용(n)으로 나누어 증명하시오.

문제를 올리면 검증된 단계별 풀이를 몇 초 만에 받을 수 있습니다.