정렬의 개념

정렬(sorting)은 원소들을 정해진 순서, 보통 오름차순이나 내림차순으로 다시 늘어놓는 일입니다. 숫자를 크기순으로, 이름을 사전순으로, 주문을 시각순으로 나열하는 것이 모두 정렬입니다. 이 장에서는 정렬이 왜 중요한지, 정렬 알고리즘을 비교할 때 쓰는 용어는 무엇인지, 그리고 실무에서 가장 자주 쓰는 "키로 정렬하기"를 살펴봅니다.

정렬이 중요한 이유

정렬 자체가 목적인 경우도 많지만, 더 자주 정렬은 다른 일을 쉽게 만드는 준비 단계입니다. 데이터가 정렬되어 있으면 다음과 같은 일이 훨씬 간단하고 빨라집니다.

• 이진 탐색: 정렬된 배열에서는 원하는 값을 O(log n)에 찾습니다.
• 중복 제거와 묶기: 같은 값이 서로 붙어 있으므로 한 번 훑으면 됩니다.
• 두 목록 합치기와 비교: 두 정렬된 목록은 포인터 두 개로 한 번에 합칠 수 있습니다.
• 구간 문제: 시작 시각으로 정렬하면 겹치는 일정, 빈 시간대를 차례로 찾을 수 있습니다.
• 순위와 상위 k개: 점수표, 검색 결과, 추천 목록은 모두 어떤 기준의 정렬입니다.

그래서 문제를 풀다 막히면 "먼저 정렬하면 쉬워지는가?"를 묻는 습관이 도움이 됩니다.

비교 정렬과 비비교 정렬

대부분의 정렬은 두 원소를 비교해 "a가 b보다 앞인가?"만 묻습니다. 이를 비교 정렬(comparison sort)이라 하며, 버블 · 삽입 · 선택 · 병합 · 퀵 · 힙 정렬이 여기에 속합니다. 비교만 쓰기 때문에 숫자, 문자열, 날짜 등 순서가 정의된 어떤 값에도 쓸 수 있습니다. 비교 정렬은 최악의 경우 Ω(n log n)번보다 적게 비교할 수 없다는 하한이 증명되어 있습니다(복잡도 장에서 다룹니다).

반대로 계수 정렬(counting sort)과 기수 정렬(radix sort)은 원소를 비교하지 않고 값 자체(정수, 자릿수)를 인덱스로 씁니다. 값의 범위가 좁거나 자릿수가 정해져 있으면 O(n)에 가깝게 정렬할 수 있지만, 아무 데이터에나 쓸 수는 없습니다.

꼭 알아야 할 용어

안정성은 여러 기준으로 정렬할 때 특히 중요합니다. 예를 들어 학생을 이름순으로 정렬한 뒤 학년으로 다시 안정 정렬하면, 같은 학년 안에서는 이름순이 그대로 남습니다.

students = [("민준", 2), ("서연", 1), ("도윤", 2), ("하은", 1)]

by_name = sorted(students, key=lambda s: s[0])
by_grade = sorted(by_name, key=lambda s: s[1])  # 안정 정렬이라 같은 학년 안에서 이름순 유지
print(by_grade)
# [('서연', 1), ('하은', 1), ('도윤', 2), ('민준', 2)]

키와 비교 함수

실무에서는 정렬 알고리즘을 직접 짜기보다 언어가 제공하는 정렬에 "무엇을 기준으로" 정렬할지 알려 주는 일이 훨씬 많습니다. Python의 sorted()와 list.sort()는 key 함수를 받습니다. key는 원소마다 한 번씩만 호출되고, 그 결과끼리 비교합니다. 튜플을 키로 쓰면 여러 기준을 한 번에 줄 수 있습니다.

orders = [
    {"id": 3, "price": 1200, "time": "10:05"},
    {"id": 1, "price": 800, "time": "09:40"},
    {"id": 2, "price": 1200, "time": "09:55"},
]

# 가격 내림차순, 가격이 같으면 시각 오름차순
ranked = sorted(orders, key=lambda o: (-o["price"], o["time"]))
print([o["id"] for o in ranked])  # [2, 3, 1]

words = ["banana", "apple", "Cherry"]
print(sorted(words))                    # ['Cherry', 'apple', 'banana'] (대문자가 먼저)
print(sorted(words, key=str.casefold))  # ['apple', 'banana', 'Cherry'] 대소문자 무시
print(sorted(words, key=len, reverse=True))

두 원소를 직접 비교하는 함수가 더 자연스러운 경우도 있습니다. C++의 std::sort, Java의 Comparator, JavaScript의 Array.prototype.sort는 비교 함수를 받습니다. Python에서는 functools.cmp_to_key로 비교 함수를 키로 바꿉니다. 비교 함수는 음수(앞), 0(같음), 양수(뒤)를 돌려주어야 하며, 항상 일관된 결과를 내야 합니다.

from functools import cmp_to_key

def by_version(a: str, b: str) -> int:
    pa = [int(x) for x in a.split(".")]
    pb = [int(x) for x in b.split(".")]
    return (pa > pb) - (pa < pb)

versions = ["1.10.0", "1.2.3", "1.2.10", "0.9"]
print(sorted(versions, key=cmp_to_key(by_version)))
# ['0.9', '1.2.3', '1.2.10', '1.10.0']

이 예는 사실 key=lambda v: [int(x) for x in v.split(".")]로도 같은 결과를 냅니다. 키 함수로 표현할 수 있으면 키 함수가 더 빠르고 실수도 적습니다.

직접 구현은 언제 하나

실제 코드에서는 거의 언제나 표준 라이브러리 정렬을 씁니다. 충분히 검증되었고, 거의 정렬된 입력이나 중복이 많은 입력 같은 현실적인 경우에 맞게 다듬어져 있기 때문입니다. 그래도 정렬 알고리즘을 직접 짜 보는 것은 가치가 있습니다. 분할 정복, 불변식, 재귀, 최악의 경우 분석 같은 알고리즘의 기본기가 모두 들어 있고, 코딩 테스트와 면접에서도 자주 나옵니다. 병합 과정을 응용한 역순 쌍 세기, 퀵 정렬의 분할을 응용한 k번째 원소 찾기처럼 정렬의 부품이 다른 문제의 핵심이 되기도 합니다.

정리

• 정렬은 그 자체보다 탐색, 중복 제거, 구간 처리 같은 다른 작업의 준비 단계로 더 자주 쓰입니다.
• 비교 정렬은 범용이지만 Ω(n log n) 하한이 있고, 계수 · 기수 정렬은 값의 성질을 이용해 이를 피합니다.
• 안정성, 제자리 여부, 적응성은 알고리즘을 고를 때 시간 복잡도만큼 중요합니다.
• 실무에서는 key 함수나 비교 함수로 기준만 정하고 내장 정렬을 쓰는 것이 기본입니다.