좌표 다중키 정렬 완벽 이해 - 알고노트

다중키 정렬이란?

다중키 정렬(Multi-key Sort)은 하나의 기준으로 순서를 못 정할 때 다음 기준을 쓰는 정렬입니다. 좌표 (x, y)처럼 값이 두 개라 한 숫자로 비교할 수 없는 데이터에 꼭 필요합니다.

규칙은 간단합니다. "먼저 x로 비교하고, x가 같을 때만 y로 비교한다." x를 1차 키, y를 2차 키라고 부릅니다.

왜 중요한가?

현실의 정렬은 대부분 다중키입니다.

• •좌표 정렬: x 순서로, 같으면 y 순서로 (계산기하·게임 맵)
• •이름 정렬: 성으로, 같으면 이름으로
• •순위표: 점수 내림차순, 같으면 시간 오름차순

코딩 테스트에서도 "x 오름차순, 같으면 y 오름차순으로 출력하라"는 조건이 자주 등장합니다.

비교 함수가 핵심

다중키 정렬의 전부는 비교 함수에 담깁니다.

compare(a, b):
    if a.x != b.x: return a.x - b.x   # 1차 키: x
    return a.y - b.y                  # 2차 키: y (x가 같을 때만)

x가 다르면 그 자리에서 결정되고, x가 같은 경우에만 y로 넘어갑니다. 이 "동점일 때만 다음 키" 흐름이 다중키의 본질입니다.

동작 원리 (예시)

points = [(3,1), (1,4), (3,0), (2,2)] 를 정렬해봅시다.

1단계. x로 줄을 세웁니다 → (1,4) / (2,2) / (3,0)·(3,1)

2단계. x가 3으로 같은 (3,0)과 (3,1)은 y로 결정 → (3,0)이 먼저

결과. [(1,4), (2,2), (3,0), (3,1)]

핵심은 (3,0)이 (3,1)보다 앞에 온다는 점입니다. 2차 키 y가 없었다면 둘의 순서는 보장되지 않았겠죠.

시간복잡도

비교 함수 자체는 O(1)입니다. 키가 몇 개든 상수 시간이므로 전체 복잡도는 사용하는 정렬 알고리즘이 결정합니다. 학습용 시각화는 비교 한 번 한 번을 보여주려고 버블정렬을 쓰지만, 실무에서는 정렬 함수에 비교자를 넘겨 O(n log n)으로 처리합니다.

자주 하는 실수

• •2차 키를 빠뜨림: x만 비교하면 x가 같은 원소들의 순서가 들쭉날쭉해집니다.
• •동점 조건 착각: x가 다를 때 y도 본다고 잘못 짜면 결과가 틀립니다. y는 x가 같을 때만 봅니다.
• •부호 혼동: 오름차순은 a - b, 내림차순은 b - a. 키마다 방향이 다를 수 있으니 주의하세요.

알고노트에서 직접 확인하세요

x를 비교하는 단계와, 동점일 때 y로 넘어가는 단계가 어떻게 나뉘는지 알고노트에서 한 스텝씩 볼 수 있습니다.

좌표 다중키 정렬 시각화 바로가기 →