정렬 문제 풀이: 커스텀 비교 함수, 안정 정렬, 코딩 테스트 정렬 패턴
이 글의 핵심
코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. Python의 sort·key 활용에 더해, Lomuto·Hoare 파티션 비교, 머지소트 보조 공간·안정성, 힙 빌드 O(n) 분석, 카운팅 정렬의 안정 배치, 스위프라인·좌표 압축 등 패턴, 그리고 DB·시스템 실무 정렬까지 한 흐름으로 정리합니다.
시리즈 안내
들어가며
코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.
기본 정렬
Python 정렬
같은 리스트를 제자리에서 정렬(sort)할지, 새 리스트를 받을지(sorted)는 원본을 유지해야 하는지에 따라 고르시면 됩니다.
# 오름차순
arr = [5, 2, 8, 1, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]
# 내림차순
arr.sort(reverse=True)
print(arr) # [9, 8, 5, 2, 1]
# 새 리스트 반환
arr = [5, 2, 8, 1, 9]
sorted_arr = sorted(arr)
print(arr) # [5, 2, 8, 1, 9] (원본 유지)
print(sorted_arr) # [1, 2, 5, 8, 9]시간 복잡도
sort(),sorted(): O(n log n) (Timsort)- 안정 정렬 보장
커스텀 정렬
key 함수
# 절댓값 기준 정렬
arr = [-5, -2, 1, 3, -8]
arr.sort(key=abs)
print(arr) # [1, -2, 3, -5, -8]
# 문자열 길이 기준
words = ["apple", "pie", "banana"]
words.sort(key=len)
print(words) # ["pie", "apple", "banana"]
# 튜플 정렬 (첫 번째 요소 기준)
students = [(85, "Alice"), (90, "Bob"), (80, "Charlie")]
students.sort()
print(students)
# [(80, 'Charlie'), (85, 'Alice'), (90, 'Bob')]다중 조건 정렬
# 점수 내림차순, 이름 오름차순
students = [
("Alice", 85),
("Bob", 90),
("Charlie", 85),
("David", 90)
]
students.sort(key=lambda x: (-x[1], x[0]))
print(students)
# [('Bob', 90), ('David', 90), ('Alice', 85), ('Charlie', 85)]
# 나이 오름차순, 이름 내림차순
people = [
("Alice", 30),
("Bob", 25),
("Charlie", 30),
]
people.sort(key=lambda x: (x[1], -ord(x[0][0])))cmp_to_key
from functools import cmp_to_key
def compare(x, y):
if x > y:
return 1
elif x < y:
return -1
else:
return 0
arr = [5, 2, 8, 1]
arr.sort(key=cmp_to_key(compare))
print(arr) # [1, 2, 5, 8]정렬 알고리즘 심화: 구현 관점
코딩 테스트에서는 보통 라이브러리 정렬을 쓰지만, 면접·설계·성능 튜닝에서는 “왜 O(n log n)인지”, “언제 깨지는지”를 묻는 경우가 많습니다. 아래는 고전 알고리즘 네 가지를 동작의 핵심만 짚은 정리입니다.
퀵소트: 파티션 내부와 피벗 선택
퀵소트(Quicksort)는 피벗(pivot) 한 개를 기준으로 배열을 작은 값 / 큰 값 두 구간으로 나누는 파티션(partition) 을 재귀적으로 반복합니다. 평균 시간 복잡도는 O(n log n), 피벗이 매번 한쪽 끝으로 치우치면 최악 O(n²) 입니다.
Lomuto 파티션은 보통 피벗을 맨 끝에 두며, i는 “피벗보다 작은 구간의 끝”, j는 스캔 인덱스로 두어 한 번의 선형 스캔으로 구간을 나눕니다. Hoare 파티션은 양쪽에서 좁혀 오며 교환하는 방식으로, 교환 횟수·캐시 특성에서 차이가 날 수 있습니다.
피벗 선택 전략은 최악 경우 완화에 직결됩니다.
- 첫/끝 요소: 구현은 단순하나, 이미 정렬된 입력에서 한쪽으로만 분할되어 O(n²) 에 가깝게 붕괴할 수 있습니다.
- 무작위 피벗: 기대적으로 균형 분할에 가까워져 평균적으로 O(n log n)에 수렴합니다.
- median-of-three(첫·중간·끝 중 중앙값): 실무 구현에서 흔히 쓰이는 타협입니다.
동일 키가 많을 때는 3-way 파티션(Dutch National Flag)으로 “작음 / 같음 / 큼” 세 구간으로 나누면 불필요한 재귀를 줄일 수 있습니다.
def lomuto_partition(arr: list, low: int, high: int) -> int:
"""피벗은 arr[high]. 반환값은 피벗의 최종 인덱스."""
pivot = arr[high]
i = low
for j in range(low, high):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quicksort_inplace(arr: list, low: int = 0, high=None) -> None:
if high is None:
high = len(arr) - 1
if low >= high:
return
p = lomuto_partition(arr, low, high)
quicksort_inplace(arr, low, p - 1)
quicksort_inplace(arr, p + 1, high)위 lomuto_partition은 안정 정렬이 아닙니다. 교환 과정에서 동일 키의 상대 순서가 바뀔 수 있습니다. 코딩 테스트용 구현을 직접 쓸 때는 스택 오버플로, 이미 정렬된 입력, 중복 많은 입력 세 가지를 특히 점검하는 것이 좋습니다.
Hoare 파티션: 양쪽에서 좁혀 오며 분할
Hoare 파티션은 피벗(보통 arr[low])을 기준으로 왼쪽 포인터 i는 피벗보다 크거나 같은 값을, 오른쪽 j는 피벗보다 작거나 같은 값을 찾아가다가 서로 교환합니다. i와 j가 교차하면 한 번의 분할이 끝납니다. 이때 피벗이 최종 위치에 놓인다는 보장은 없습니다. 대신 왼쪽 구간의 모든 원소 ≤ 오른쪽 구간의 모든 원소라는 불변식이 성립하며, 재귀는 보통 [low, j]와 [j+1, high]처럼 겹치지 않게 나눕니다.
def hoare_partition(arr: list, low: int, high: int) -> int:
"""피벗은 arr[low]. 반환값 j: [low, j]와 [j+1, high]로 재귀."""
pivot = arr[low]
i, j = low - 1, high + 1
while True:
while True:
i += 1
if arr[i] >= pivot:
break
while True:
j -= 1
if arr[j] <= pivot:
break
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quicksort_hoare(arr: list, low: int = 0, high=None) -> None:
if high is None:
high = len(arr) - 1
if low >= high:
return
p = hoare_partition(arr, low, high)
quicksort_hoare(arr, low, p)
quicksort_hoare(arr, p + 1, high)Lomuto vs Hoare를 면접·구현 관점에서 정리하면 다음과 같습니다.
| 항목 | Lomuto | Hoare |
|---|---|---|
| 피벗 최종 위치 | 파티션 끝에 확정 (p가 피벗 인덱스) | 일반적으로 확정되지 않음 |
| 분할 균형 | 피벗이 한쪽 끝이면 불균형 위험 | 평균적으로 조금 더 균형인 경우가 많음 |
| 교환 횟수 | 동일 키가 많으면 불필요 교환이 잦을 수 있음 | 교환 횟수가 적은 편으로 알려짐 |
| 재귀 범위 | quicksort(low, p-1), (p+1, high)로 단순 | [low, p], [p+1, high] 등 경계 오프바이원에 유의 |
| 파티션 후 | 한쪽에 피벗 하나가 고정 | 두 구간 모두 비어 있지 않게 분할(전형적 구현) |
동일 키가 매우 많을 때는 앞서 언급한 3-way 파티션과 함께, Lomuto의 <= 비교와 스캔 순서가 성능·교환 횟수에 미치는 영향을 설명할 수 있으면 설득력이 높습니다.
머지소트: 안정성 분석
안정 정렬(stable sort) 이란, 정렬 키가 같은 원소들의 입력에서의 상대 순서가 출력에서도 유지되는 성질입니다.
머지소트(Mergesort)는 배열을 반으로 나누어 각각 정렬한 뒤 병합(merge) 할 때, 왼쪽 절반에서 가져온 원소를 오른쪽과 키가 같을 때 우선 하면 됩니다. 즉, 병합 단계에서 left[i] <= right[j]일 때 왼쪽을 먼저 넣는 규칙 하나로 안정성이 보장됩니다. 반대로 오른쪽을 먼저 넣으면 동일 키의 상대 순서가 뒤바뀔 수 있습니다.
증명의 직관: 동일 키 a와 b(입력에서 a가 앞)가 서로 다른 절반에 있다고 해도, 병합 시 항상 “왼쪽 절반의 원소를 먼저” 소진하는 규칙이면 a가 b보다 먼저 출력 구간에 놓입니다. 키가 다른 쌍에 대해서는 비교 결과가 순서를 결정하며, 키가 같은 쌍만 위 규칙이 tie-breaker 역할을 합니다.
시간은 항상 O(n log n) 이고, 단점은 O(n) 보조 공간이 필요하다는 점입니다. Python의 list.sort()는 Timsort로 안정 정렬이며, 멀티 패스 정렬(키가 여러 단계일 때)을 설계할 때 “한 번의 안정 정렬로 단계별 조건을 쌓는” 패턴과 잘 맞습니다.
보조 공간 최적화: 완전 제자리(in-place) 머지의 현실
표준 머지소트는 길이 n인 임시 배열에 병합 결과를 쓰므로 Ω(n) 보조 공간이 하한입니다. “O(1) 보조 공간으로 병합”을 목표로 하는 in-place merge 알고리즘들은 이론·연구 주제로 오래되었으나, 비교 횟수·캐시·구현 복잡도 때문에 범용 라이브러리의 기본 머지에는 잘 쓰이지 않습니다.
실무·교과서에서 자주 등장하는 완화책은 다음과 같습니다.
- 버퍼 크기 줄이기: 예를 들어 짧은 구간만 임시 배열에 복사하고 나머지는 회전·블록 교환 등으로 맞추는 block merge 계열(구현 난이도 높음).
- 연결 리스트: 노드를 끊어 붙이는 방식이면 추가 포인터만으로 병합 가능하지만, 배열 기반 정렬과는 문제 설정이 다릅니다.
- 바텀업(bottom-up) 머지: 재귀 스택 대신 같은 임시 버퍼를 레벨마다 재사용하면, “스택 공간”은 줄일 수 있으나 입력 크기만큼의 버퍼 자체는 그대로인 경우가 일반적입니다.
정리하면, 코딩 테스트·대부분의 서비스 코드에서는 O(n) 보조 공간 머지를 전제로 한 표준 머지소트가 이해·검증이 쉽으며, “공간 O(1)”은 문제에서 명시적으로 요구할 때만 in-place 병합·힙소트·라이브러리의 다른 전략을 비교하는 것이 합리적입니다.
힙소트: 힙 속성 유지
이진 힙(binary heap) 은 완전 이진 트리로 표현하며, 최대 힙에서는 각 노드의 값이 자식 값보다 크거나 같다는 힙 속성(heap property) 을 유지합니다. 배열 인덱스로는 노드 i의 자식이 2i+1, 2i+2(0-based)입니다.
힙소트(Heapsort)는 (1) 배열을 최대 힙으로 빌드하며, (2) 루트(최댓값)를 끝과 바꾼 뒤 힙 크기를 줄이고 아래로 내려가며(sift-down / heapify) 힙 속성을 복구하는 과정을 반복합니다. sift-down 한 번은 트리 높이에 비례해 O(log n) 이고, 이 추출·복구를 n-1번 반복하므로 정렬 단계 전체는 O(n log n) 입니다. 제자리(in-place) 정렬이라 보조 배열이 거의 필요 없다는 장점이 있습니다.
빌드(heapify)가 O(n)인 이유: 높이 합 논증
초심자에게 흔한 오해는 “n/2개 노드에서 각각 sift-down 하니 O(n log n) 아닌가?” 하는 것입니다. 결론만 말하면 전체 빌드는 O(n) 입니다.
완전 이진 트리에서 높이 h인 레벨(말단에 가까운 쪽) 에 있는 노드 수는 대략 O(n / 2^(h+1)) 수준이며, 그 노드 하나의 sift-down 비용은 O(h) 입니다. 전체 비용은 높이에 대해 합산하면 대략
[ \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot O(h) = O(n) ]
(많은 노드는 낮은 높이, 높은 노드는 소수이기 때문입니다.) 반면 정렬 단계에서 루트를 n-1번 뽑을 때마다 sift-down은 매번 O(log n) 이므로 O(n log n) 이 됩니다. 즉 힙 구축은 선형, 추출·복구 반복이 n log n 이라고 기억하면 면접 답변이 깔끔합니다.
def _sift_down(arr: list, n: int, i: int) -> None:
"""구간 [0, n)을 힙으로 볼 때 i에서 아래로 힙 속성 복구."""
while True:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest == i:
return
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heapsort(arr: list) -> None:
n = len(arr)
# 아래 인덱스부터 sift-down → O(n) 빌드
for i in range(n // 2 - 1, -1, -1):
_sift_down(arr, n, i)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
_sift_down(arr, end, 0)힙소트는 일반적으로 안정 정렬이 아닙니다(교환으로 동일 키 순서가 바뀔 수 있음). 최악 시간 O(n log n) 이라는 점은 퀵소트와 대비될 때 자주 언급됩니다.
카운팅 정렬: 빈도와 위치(버킷 분배)
카운팅 정렬(Counting sort) 은 키가 작은 정수 범위에 속할 때, 각 값의 개수를 세고, 누적 합으로 출력 위치를 정한 뒤 한 번에 옮겨 넣습니다. 여기서 “버킷”은 흔히 값 → 해당 값이 들어갈 구간의 다음 빈 슬롯을 가리키는 위치 배열로 구현합니다.
단계는 (1) count[v]에 빈도 누적, (2) count를 접두 합(prefix sum) 으로 바꿔 “끝 위치”를 잡으며, (3) 입력을 역순으로 스캔하며 안정적으로 출력 배열에 놓는 방식이 대표적입니다. 키 범위를 k라 하면 시간·공간은 O(n + k) 입니다. k >> n이면 비실용적입니다.
def counting_sort_stable(arr: list[int], k: int) -> list[int]:
"""arr 원소는 0 이상 k 미만 정수라고 가정."""
count = [0] * k
for x in arr:
count[x] += 1
for i in range(1, k):
count[i] += count[i - 1]
out = [0] * len(arr)
for x in reversed(arr):
count[x] -= 1
out[count[x]] = x
return out안정성: 접두 합 이후에 왜 입력을 역순으로 넣는가
카운팅 정렬이 안정하려면, 같은 키를 가진 원소들이 입력에서의 상대 순서가 출력에서도 유지되어야 합니다. 접두 합으로 count[v]를 바꾼 뒤의 의미는 “값 v를 넣을 때 사용할 다음 인덱스(또는 구간 끝)”입니다. 이때 입력을 앞에서부터 넣으면, 뒤에 있던 동일 키가 앞선 원소보다 먼저 출력 슬롯을 차지해 상대 순서가 뒤집힐 수 있습니다. 역순 스캔은 “같은 키 중 나중에 등장한 원소가 더 앞쪽 슬롯을 쓰도록” 맞춰, 결과적으로 입력 순서가 보존되게 합니다.
비안정 변형으로 앞에서부터 채우는 구현도 만들 수 있으나, 그 경우 인덱스를 왼쪽 끝부터 쓰는 규칙과 키 분포를 정확히 맞춰야 하며, 교과서·면접에서 말하는 “표준 안정 카운팅 정렬”은 위처럼 누적 위치 + 역방향 배치 조합이 대표적입니다. 기수 정렬이 낮은 자릿수부터 안정 정렬을 반복해도 전체 순서가 맞는 이유도, 매 단계의 부분 정렬이 안정해야 하기 때문입니다.
기수 정렬(Radix sort) 은 자릿수별로 위와 같은 안정한 부분 정렬(종종 카운팅 정렬)을 반복해 큰 정수 범위를 다루는 방식으로 확장됩니다. “버킷 분배”를 인덱스 버킷으로 보면, 카운팅 정렬은 가장 단순한 형태의 분배·수집이라고 이해할 수 있습니다.
실전 문제
문제 1: 가장 큰 수
def largest_number(nums):
"""
숫자를 이어 붙여 가장 큰 수
[3, 30, 34, 5, 9] → "9534330"
"""
from functools import cmp_to_key
def compare(x, y):
if x + y > y + x:
return -1
elif x + y < y + x:
return 1
else:
return 0
nums_str = list(map(str, nums))
nums_str.sort(key=cmp_to_key(compare))
result = ''.join(nums_str)
return '0' if result[0] == '0' else result
print(largest_number([3, 30, 34, 5, 9])) # "9534330"
print(largest_number([0, 0, 0])) # "0"문제 2: H-Index
def h_index(citations):
"""
h번 이상 인용된 논문이 h편 이상
[3, 0, 6, 1, 5] → 3
"""
citations.sort(reverse=True)
h = 0
for i, citation in enumerate(citations):
if citation >= i + 1:
h = i + 1
else:
break
return h
print(h_index([3, 0, 6, 1, 5])) # 3
print(h_index([10, 8, 5, 4, 3])) # 4문제 3: 구간 합치기
def merge_intervals(intervals):
"""
겹치는 구간 합치기
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
"""
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]:
merged[-1] = [last[0], max(last[1], current[1])]
else:
merged.append(current)
return merged
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))
# [[1, 6], [8, 10], [15, 18]]문제 4: 회의실 배정
def max_meetings(meetings):
"""
겹치지 않는 최대 회의 수
[(1, 4), (3, 5), (0, 6), (5, 7)] → 3
"""
meetings.sort(key=lambda x: x[1])
count = 0
last_end = 0
for start, end in meetings:
if start >= last_end:
count += 1
last_end = end
return count
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings)) # 4정렬 활용 패턴
패턴 1: 정렬 + 투 포인터
def two_sum_sorted(arr, target):
"""
정렬 후 투 포인터로 합 찾기
"""
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [arr[left], arr[right]]
elif current_sum < target:
left += 1
else:
right -= 1
return None
print(two_sum_sorted([2, 7, 11, 15], 9)) # [2, 7]패턴 2: 정렬 + 이진 탐색
from bisect import bisect_left
def count_smaller(arr, target):
"""
정렬 후 이진 탐색
"""
arr.sort()
idx = bisect_left(arr, target)
return idx
arr = [5, 2, 8, 1, 9]
print(count_smaller(arr, 6)) # 3 (1, 2, 5)패턴 3: 정렬 + 그리디
def assign_cookies(children, cookies):
"""
아이들에게 쿠키 배정 (최대 만족)
"""
children.sort()
cookies.sort()
i = j = 0
while i < len(children) and j < len(cookies):
if cookies[j] >= children[i]:
i += 1
j += 1
return i
children = [1, 2, 3]
cookies = [1, 1]
print(assign_cookies(children, cookies)) # 1패턴 4: 정렬 + 스위프라인(이벤트 순서)
구간·직사각형·스케줄 겹침 등에서 시작/끝 이벤트를 시간 순으로 처리할 때, 먼저 좌표 또는 시간으로 정렬해 스캔 순서를 고정합니다. 전형적으로 (위치, 종류) 튜플을 쓰며, 같은 좌표에서는 닫힘보다 열림 등 문제가 요구하는 태이브레이크를 둡니다.
# 예: 구간 [l, r]을 이벤트로 펼친 뒤 정렬해 겹침 깊이 스캔(경계 처리는 문제 정의에 맞게 조정)
def max_overlap_depth(intervals):
events = []
for l, r in intervals:
events.append((l, 1)) # 시작
events.append((r, -1)) # 끝
# 같은 좌표에서는 두 번째 값 -1(끝)이 1(시작)보다 앞서 오도록 기본 튜플 정렬 사용
events.sort()
depth = best = 0
for _, delta in events:
depth += delta
best = max(best, depth)
return best패턴 5: 좌표 압축 후 카운팅·순위
값의 범위는 크지만 서로 다른 값의 개수는 작을 때, 정렬로 순위 맵을 만든 뒤 0 .. m-1 키로 바꿔 세그먼트 트리·BIT·카운팅 정렬에 넣는 패턴이 흔합니다.
def compress(values):
uniq = sorted(set(values))
return {v: i for i, v in enumerate(uniq)}패턴 6: 정렬 기준을 “한 번에” — 파이썬 키 vs 비교기
key=lambda x: (x.a, -x.b)처럼 튜플 키로 대부분의 다중 조건을 표현하며, 전역 순서가 임의일 때만 cmp_to_key를 씁니다. 비교 함수는 대칭성·추이성 실수가 나오기 쉬우므로, 가능하면 키 튜플로 환원하는 편이 안전합니다.
패턴 7: 정렬 후 동일 그룹 묶기(itertools.groupby)
연속한 동일 키만 묶이므로, 반드시 먼저 정렬합니다. “전체에서 같은 값끼리”가 아니라 인접 그룹이라는 점에 주의합니다.
from itertools import groupby
items = [(1, "a"), (1, "b"), (2, "c")]
items.sort(key=lambda x: x[0])
for k, g in groupby(items, key=lambda x: x[0]):
print(k, list(g))패턴 8: 부분 순위만 필요할 때 — 전체 정렬 대신 힙/Quickselect
상위 k개 또는 k번째만 필요하면 O(n log n) 전체 정렬 대신 크기 k 최소 힙이나 Quickselect(평균 O(n)) 가 유리한 경우가 많습니다. 다만 Quickselect는 최악 O(n²) 이 될 수 있어, 라이브러리·랜덤 피벗·introspection 조합 등 문제 제약을 확인합니다.
프로덕션 정렬 패턴
애플리케이션 코드에서 sort() 호출 한 줄 뒤에는 언어런타임, 데이터베이스, 스토리지·인덱스가 각각 다른 정렬 전략을 씁니다. 실무에서는 “알고리즘 이름”보다 데이터 크기, 키 타입, 안정성, 메모리, 디스크, 이미 정렬된 구간 활용이 결정을 나눕니다.
언어 런타임
- Python
list.sort/ Timsort: 실제 데이터에 이미 정렬된 구간(run) 이 많다는 가정에서 잘 동작하며, 안정 정렬입니다. 대부분의 코딩 테스트·서비스 코드에서는 직접 퀵소트를 구현하지 않는 것이 유지보수·정확성 면에서 이득입니다. - C++
std::sort: 일반적으로 introsort(퀵소트 + 힙소트로 최악 완화) 계열이며,std::stable_sort는 안정 정렬이 필요할 때 별도로 선택합니다. - Java
Arrays.sort: primitive와Object에 따라 알고리즘이 달라질 수 있어, 문서를 확인하는 것이 안전합니다.
데이터베이스와 쿼리
ORDER BY: 실행 계획에서 인덱스 스캔으로 정렬을 피하거나, 메모리 정렬 + 디스크 스필로 처리합니다. 대용량이면 “애플리케이션에서 전부 정렬”이 아니라 DB에 맡기고 LIMIT·인덱스로 줄이는 쪽이 맞는 경우가 많습니다.- 복합 정렬:
(a DESC, b ASC)는 코딩 테스트의 튜플key와 같은 다중 키 문제이며, 안정 정렬 + 단일 키 정렬을 여러 번 적용하는 트릭과 이론적으로 연결됩니다.
대용량·외부 정렬
- 메모리에 다 들어가지 않으면 외부 정렬(external sort) (예: 런을 나눠 정렬 후 k-way merge)가 사용됩니다. 로그·ETL·온디스크 인덱스 빌드에서 흔한 패턴입니다.
언제 특수 정렬을 고려할까
- 키가 좁은 범위의 정수이면 카운팅·기수 정렬이 O(n)에 가깝게 이길 수 있습니다.
- 부분 정렬(상위 k개만 필요)이면 전체 정렬 대신 힙이나 quickselect가 더 낫습니다.
- 안정성이 필요하면(동일 키의 입력 순서 유지) 머지소트·Timsort 계열을 선택합니다.
실무 체크리스트
- 정렬이 병목인가? 프로파일링 전에
key함수가 무거운지(객체 속성 접근 반복)부터 확인합니다. - 이미 정렬된 입력이 많은가? Timsort류는 이득이며, 역순에 가까운 입력은 구현에 따라 덜 유리할 수 있습니다.
- 최악 시간이 중요한가? 퀵소트 단독 구현은 피하며, 라이브러리·introsort·힙소트 등 최악 보장을 확인합니다.
- 중복·타이가 많은가? 3-way 파티션, 다중 키 설계, 안정 정렬 필요 여부를 검토합니다.
추천 문제와 비교 함수 함정
정렬 문제에서 가장 많이 틀리는 곳은 비교 함수입니다. functools.cmp_to_key에 넘기는 함수는 True/False가 아니라 음수·0·양수를 돌려줘야 하는데, return a > b처럼 불리언을 반환하면 에러 없이 엉뚱한 순서가 나옵니다. 프로그래머스 “가장 큰 수”가 대표적인 예로, 두 숫자 문자열 a, b를 a + b와 b + a로 이어 붙여 비교해야 하고, 입력이 모두 0일 때 "000"이 아니라 "0"을 돌려주는 예외 처리까지 해야 통과합니다. 다중 조건 정렬은 가능하면 비교 함수 대신 튜플 키(key=lambda x: (x[1], x[0]))로 표현하는 편이 실수가 적습니다.
백준:
프로그래머스:
LeetCode:
정렬 알고리즘 자체의 동작이 궁금하다면 정렬 기초와 고급 정렬을, 정렬 뒤에 상태를 쌓아 가는 문제로 넘어가려면 동적 프로그래밍을 이어서 보면 됩니다.
같이 보면 좋은 글
- 배열과 연결 리스트
- 기초 정렬 알고리즘
- 이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치
- DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
- C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선
- 고급 정렬: 퀵·병합·힙 정렬이 O(n log n)인 이유와 선택 기준
자주 묻는 질문 (FAQ)
Q. ‘가장 큰 수’ 문제는 왜 key 함수가 아니라 cmp_to_key로 정렬하나요?
A. 이 문제의 정렬 기준은 두 숫자 문자열 x, y를 x+y와 y+x로 이어 붙여 어느 쪽이 더 큰지 비교하는 것이라, 원소 하나만 보고 값을 만드는 key 함수로는 표현하기 어렵습니다. 그래서 두 원소를 받아 -1, 0, 1을 돌려주는 비교 함수를 만들고 functools.cmp_to_key로 감싸 sort에 넘깁니다. 입력이 [0, 0, 0]이면 결과가 “000”이 되므로 첫 글자가 ‘0’일 때 “0”을 반환하는 처리도 필요합니다.