정렬 알고리즘

정렬 알고리즘은 뒤섞인 값을 정해진 순서대로 다시 늘어놓아 줍니다. 값을 줄 세워 두면 찾고 합치는 뒷일이 빨라집니다. 줄 세우는 방법은 여러 가지입니다. 방법마다 드는 시간과 메모리가 다릅니다.

상세

이 절은 정렬의 입력과 출력, 정렬이 싸게 만드는 일, 정렬 시간이 줄어들 수 있는 한계, 방법을 가르는 성질을 차례로 봅니다. 방법 하나하나의 절차는 각 방법의 항목이 다룹니다.

정렬이 받는 것과 내주는 것

값을 순서대로 늘어놓는 일을 정렬이라고 합니다. 정렬 알고리즘은 그 일을 해내는 절차입니다. 넣는 것은 값의 목록입니다. 나오는 것은 그 값들을 순서대로 늘어놓은 목록입니다.

「순서대로」에는 기준이 있어야 합니다. 주문 목록이라면 금액이 기준이 될 수 있습니다. 주문 시각이 기준이 될 수도 있습니다. 이렇게 정렬하는 데 쓰는 값을 정렬 키라고 부릅니다.

기준이 정해지면 두 값 가운데 어느 쪽이 앞인지를 가릴 수 있어야 합니다. 이 판정을 맡는 함수를 비교 함수라고 합니다. 두 값을 받아 「앞이다 · 뒤다 · 같다」 가운데 하나를 돌려줍니다.

비교 함수는 약속 하나를 지켜야 합니다. a 가 b 보다 앞이고 b 가 c 보다 앞이면 a 도 c 보다 앞이어야 합니다. 이 약속이 깨지면 정렬이 돌려준 목록이 순서대로 놓였다고 믿을 수 없습니다.

어떤 두 값이든 앞뒤를 가릴 수 있으면서 이 약속까지 지키는 순서를 전순서라고 합니다. 정렬 알고리즘은 값들 사이에 전순서가 있다고 가정하고 돕니다.

파이썬의 sorted 함수로 보면 이렇습니다. 둘째 줄은 기준을 따로 주지 않았습니다. 셋째 줄은 글자 수를 정렬 키로 삼았습니다.

w = ["plum", "fig", "kiwi"]
sorted(w)           # ['fig', 'kiwi', 'plum']
sorted(w, key=len)  # ['fig', 'plum', 'kiwi']

기준을 안 주면 문자열은 알파벳 순으로 놓입니다. key=len 은 값마다 글자 수를 재어 그것으로 정렬하라는 뜻입니다. 같은 목록이 기준에 따라 다른 순서로 나왔습니다.

셋째 줄에서 plum 과 kiwi 는 둘 다 네 글자라 기준으로는 같습니다. 이때 원래 목록에서 앞에 있던 plum 이 먼저 나왔습니다. 이 성질은 뒤의 「같은 값끼리의 순서」 소절에서 다시 봅니다.

정렬해 두면 싸지는 일

정렬은 그 자체로 쓰일 때도 있습니다. 목록을 금액 순으로 화면에 보여 줄 때입니다. 그런데 더 큰 쓸모는 정렬 뒤에 오는 일을 싸게 만드는 데 있습니다. 이 소절은 그런 일 셋을 봅니다.

첫째는 찾기입니다. 정렬하지 않은 목록에서 값 하나를 찾으려면 처음부터 끝까지 훑어야 합니다. 정렬된 목록에서는 가운데 값을 보고 찾는 값이 없는 쪽 절반을 버립니다.

이 버리기를 되풀이하는 찾기가 이진 탐색입니다. 값이 백만 개면 훑기는 최악일 때 백만 번을 봅니다. 이진 탐색은 스무 번쯤 보면 끝납니다.

둘째는 같은 값 모으기입니다. 정렬하면 같은 값이 서로 이웃합니다. 그래서 바로 옆 값끼리만 비교하면 중복 제거가 끝납니다. 정렬하지 않았다면 모든 값을 다른 모든 값과 비교해야 합니다.

셋째는 합치기입니다. 이미 정렬된 두 목록은 맨 앞 값끼리만 비교합니다. 그렇게 한 번 훑으면 하나로 합칠 수 있습니다. 데이터베이스가 두 테이블을 키 순서로 맞대어 잇는 병합 조인이 이 성질을 씁니다.

정렬 비용은 한 번 치르고 그 뒤의 찾기와 합치기에서 여러 번 거둡니다. 거꾸로 값 하나를 딱 한 번만 찾을 거라면 정렬하는 비용이 목록을 한 번 훑는 비용보다 큽니다. 그 까닭은 다음 소절의 시간 표기에서 드러납니다.

걸리는 시간을 적는 법

정렬 방법을 비교할 때는 값이 늘어날 때 시간이 어떻게 따라 느는지를 봅니다. 값의 개수를 n 이라고 적습니다.

빅오 표기법은 이 늘어나는 모양을 적는 약속입니다. O(n) 은 값이 두 배가 되면 시간도 두 배쯤 된다는 뜻입니다. O(n²) 은 값이 두 배가 되면 시간이 네 배쯤 된다는 뜻입니다.

O(n log n) 은 그 사이에 있습니다. log n 은 n 을 1 이 될 때까지 반으로 나눈 횟수입니다. 1,000 은 열 번쯤 나누면 1 이 됩니다. 1,000,000 은 스무 번쯤 나누면 1 이 됩니다.

단순한 정렬 방법은 값 하나를 제 위치에 놓을 때마다 나머지 값들을 훑습니다. 그래서 O(n²) 입니다. 목록을 반씩 나눠 다루는 방법은 O(n log n) 에 끝냅니다. 아래 표는 두 모양이 얼마나 벌어지는지 어림으로 보입니다.

값이 백만 개면 한쪽은 이천만 번쯤 일합니다. 다른 쪽은 조 단위로 일합니다. 정렬 방법을 고를 때 가장 먼저 보는 것이 이 차이입니다.

한 번 훑기는 O(n) 입니다. 비교해서 정렬하는 방법은 잘해야 O(n log n) 이라 한 번 훑기보다 log n 배쯤 더 듭니다. 앞 소절에서 「한 번만 찾을 거라면 정렬이 더 비싸다」고 한 까닭이 이것입니다.

비교해서 정렬하는 방법이 왜 O(n log n) 보다 줄어들 수 없는지는 다음 소절이 봅니다.

비교 정렬의 하한

값끼리 비교하는 것 말고 다른 정보를 쓰지 않는 정렬을 비교 정렬이라고 합니다. 이름난 정렬 방법은 대부분 여기 듭니다. 이 소절은 비교 정렬이 아무리 잘 짜여도 넘을 수 없는 시간의 선, 곧 하한을 봅니다.

값 세 개 a · b · c 를 정렬한다고 해 봅시다. 가능한 순서는 a·b·c, a·c·b, b·a·c, b·c·a, c·a·b, c·b·a 여섯 가지입니다. 정렬은 이 여섯 가운데 어느 것이 맞는지를 알아내는 일입니다.

비교 한 번의 답은 「예」 아니면 「아니오」 둘뿐입니다. 그래서 비교 한 번은 남은 후보를 기껏해야 절반으로 줄입니다. 아래 그림은 세 값을 비교하는 모든 경우를 가지로 펼친 것입니다.

flowchart TD
    Q1{"a ≤ b ?"}
    Q1 -->|예| Q2{"b ≤ c ?"}
    Q1 -->|아니오| Q3{"a ≤ c ?"}
    Q2 -->|예| L1["a·b·c"]
    Q2 -->|아니오| Q4{"a ≤ c ?"}
    Q4 -->|예| L2["a·c·b"]
    Q4 -->|아니오| L3["c·a·b"]
    Q3 -->|예| L4["b·a·c"]
    Q3 -->|아니오| Q5{"b ≤ c ?"}
    Q5 -->|예| L5["b·c·a"]
    Q5 -->|아니오| L6["c·b·a"]

마름모 하나가 비교 한 번입니다. a ≤ b 는 a 가 b 보다 앞이거나 같은가를 묻습니다. 맨 아래 여섯 칸이 가능한 순서 여섯 가지입니다. 이렇게 비교를 가지로 펼친 그림을 결정 트리라고 부릅니다.

맨 위에서 맨 아래까지 가장 긴 길은 비교 세 번입니다. 비교 두 번으로는 네 갈래까지만 가를 수 있어서 여섯 후보를 다 못 가릅니다. 그래서 어떤 비교 정렬도 세 값을 최악일 때 세 번보다 적게 비교하고는 못 끝냅니다.

값이 늘면 후보도 빠르게 늘어납니다. 값이 n 개면 가능한 순서는 1 부터 n 까지 모두 곱한 수만큼 있습니다. 이 수를 n! 이라고 적습니다. 값이 열 개면 3,628,800 가지입니다.

3,628,800 가지를 절반씩 줄여 하나를 남기려면 스물두 번을 비교해야 합니다. 값이 n 개면 n! 을 1 이 될 때까지 반으로 나눈 횟수만큼 비교해야 합니다.

n! 에서 곱하는 수 n 개 가운데 절반쯤은 n/2 보다 큽니다. 그러니 n! 은 n/2 를 n/2 번 곱한 수보다 큽니다. 이 수를 1 이 될 때까지 반으로 나누는 횟수는 n/2 × log(n/2) 이고, n log n 과 같은 모양으로 늘어납니다. 따라서 비교 정렬은 최악일 때 O(n log n) 보다 빠를 수 없습니다.

비교하지 않는 정렬

앞 소절의 하한은 비교만 할 때의 이야기입니다. 값에 대해 더 아는 것이 있으면 비교하지 않고도 정렬할 수 있습니다. 이 소절은 값의 범위를 미리 알 때를 봅니다.

값이 0 부터 3 까지의 정수뿐이라고 해 봅시다. 칸 네 개를 만듭니다. 값을 하나 읽을 때마다 그 값의 칸에 적힌 수를 하나 올립니다. 다 세고 나면 0 칸부터 센 수만큼 값을 꺼내 늘어놓습니다.

이 과정에서 값끼리는 한 번도 비교하지 않았습니다. 이 방식을 계수 정렬이라고 합니다.

시간은 목록을 한 번, 칸을 한 번 훑는 만큼 듭니다. 값이 가질 수 있는 범위의 크기를 k 라고 하면 O(n + k) 입니다.

대가는 범위입니다. 값이 0 부터 40억까지라면 칸이 40억 개 필요합니다. 그래서 이 방식은 범위가 좁은 정수에만 씁니다.

자릿수가 많은 정수는 자릿수 하나씩 끊어 이 세기를 되풀이합니다. 이것이 기수 정렬입니다. 자릿수 하나는 0 부터 9 까지라 칸이 열 개면 됩니다.

같은 값끼리의 순서

정렬 방법들은 시간 말고도 몇 가지 성질로 갈립니다. 이 소절과 다음 소절이 그 성질 둘을 봅니다. 먼저 정렬 키가 같은 값끼리의 순서입니다.

정렬 키가 같은 값이 여럿일 때 원래 목록의 앞뒤 순서를 지키는 정렬을 안정 정렬이라고 합니다. 앞의 코드에서 plum 과 kiwi 가 원래 순서대로 나온 것이 이 성질입니다.

이 성질은 정렬을 두 번 할 때 쓸모가 있습니다. 주문 목록을 시각 순으로 정렬해 둔 뒤 금액 순으로 다시 정렬한다고 해 봅시다.

금액 순으로 다시 정렬하면 3,000 원 주문이 맨 앞에 옵니다. 5,000 원 주문 두 건은 정렬 키가 같습니다. 안정 정렬은 이 둘을 원래대로 09:00 → 09:20 순서로 남깁니다.

결과는 금액 순입니다. 금액이 같으면 시각 순입니다. 두 기준으로 정렬한 효과를 정렬 두 번으로 얻습니다. 안정하지 않은 정렬은 금액이 같은 주문끼리의 시각 순서를 흩뜨릴 수 있습니다.

추가로 드는 메모리

두 번째 성질은 정렬하는 동안 메모리를 얼마나 더 쓰는지입니다. 값이 많으면 이 차이가 방법을 가릅니다.

원래 목록 안에서 값을 맞바꾸기만 하며 정렬하는 방식을 제자리 정렬이라고 합니다. 값 몇 개를 잠시 담아 둘 공간이면 충분합니다. 이 공간은 값이 아무리 많아도 몇 칸으로 일정해서 O(1) 이라고 적습니다.

반대로 병합 정렬은 합친 결과를 담을 목록을 하나 더 씁니다. 백만 개를 정렬하면 백만 칸이 더 필요합니다. 이 추가 공간을 O(n) 이라고 적습니다.

이름난 정렬 방법

이름난 정렬 방법들을 앞의 성질로 나란히 놓습니다. 먼저 각 방법이 어떤 식으로 정렬하는지를 한 줄씩 봅니다.

위의 여섯은 비교 정렬입니다. 아래 둘은 비교하지 않는 정렬입니다. 다음 표는 같은 방법들을 시간과 추가 공간과 안정성으로 놓은 것입니다. 기수 정렬 줄의 d 는 자릿수이고, k 는 자릿수 하나가 가질 수 있는 값의 수(10진수면 10)입니다.

표에서 먼저 볼 것은 위의 세 줄입니다. 시간은 O(n²) 입니다. 대신 추가 공간이 몇 칸뿐입니다. 절차가 짧아 값이 몇십 개일 때는 O(n log n) 방법보다 먼저 끝나기도 합니다.

삽입 정렬은 목록이 이미 거의 정렬되어 있으면 끼워 넣을 때 몇 칸만 옮깁니다. 그런 목록에서는 O(n) 에 가깝게 끝납니다. 입력이 얼마나 정렬되어 있는지에 따라 빨라지는 이런 성질을 적응 정렬이라고 부릅니다.

퀵 정렬은 보통일 때와 최악일 때가 다릅니다. 기준값이 계속 가장 작은 값이나 가장 큰 값으로 뽑히면 한쪽이 거의 빈 채로 분할됩니다. 그러면 O(n²) 까지 느려집니다.

퀵 정렬은 값을 원래 목록 안에서 맞바꾸며 분할해서 흔히 제자리 정렬로 칩니다. 그래도 분할한 조각 가운데 아직 처리하지 않은 것을 기억해 둘 공간이 듭니다. 이 공간은 다시 분할한 횟수, 곧 분할의 깊이만큼입니다. 보통은 log n 번쯤 거듭 분할하면 조각이 하나씩 남아서 O(log n) 입니다.

병합 정렬과 힙 정렬은 최악일 때도 O(n log n) 입니다. 비교 정렬의 하한에 닿아 있습니다. 그 대신 병합 정렬은 O(n) 의 추가 공간을 씁니다. 힙 정렬은 안정성을 내줍니다.

여러 방법을 섞은 정렬

언어의 표준 라이브러리가 내주는 정렬 함수는 한 방법만 쓰지 않는 경우가 많습니다. 방법마다 빨리 끝나는 조건이 달라서 둘셋을 섞습니다. 이 소절은 그렇게 섞은 대표 둘을 봅니다.

팀 정렬은 병합 정렬과 삽입 정렬을 섞었습니다. 목록 안에 이미 정렬된 구간이 있으면 그 구간을 조각으로 삼아 병합 정렬처럼 합칩니다. 짧은 구간은 삽입 정렬로 정렬합니다.

인트로 정렬은 퀵 정렬로 시작합니다. 분할이 너무 깊어져 최악으로 흐르는 기미가 보이면 힙 정렬로 바꿉니다. 조각이 작아지면 삽입 정렬로 마무리합니다.

상황마다 고르는 방법

백엔드 코드에서 정렬을 직접 짜는 일은 드뭅니다. 대개 표준 라이브러리의 정렬 함수를 부릅니다. 그래도 그 함수가 무엇을 약속하는지는 알아야 합니다.

그래야 결과를 믿어도 되는지 판단할 수 있습니다. 비용도 어림할 수 있습니다.

외부 정렬은 데이터를 메모리에 들어갈 만큼씩 잘라 각각 정렬해 디스크에 쓰는 방식입니다. 그다음 정렬된 파일들을 앞에서부터 읽으며 합칩니다.

가장 큰 몇 개만 필요할 때는 전체를 정렬하는 비용을 치를 까닭이 없습니다. 가장 큰 값을 빨리 꺼내 주는 이진 힙에 담아 몇 개만 꺼내면 됩니다. 이런 질의를 상위 N 질의라고 부릅니다.

정렬을 아예 안 하는 길도 있습니다. 데이터베이스의 인덱스는 값을 정렬된 채로 들고 있습니다.

질의가 ORDER BY 로 순서를 요구할 수 있습니다. 인덱스가 그 순서를 이미 갖고 있으면 다시 정렬하지 않습니다. 인덱스 순서대로 읽기만 합니다.

관련 항목

정렬 알고리즘이 속하는 상위 분류

알고리즘 · 정렬 · 비교 정렬 · 분할 정복 · 계산 문제

정렬 알고리즘의 하위 종류

버블 정렬 · 선택 정렬 · 삽입 정렬 · 셸 정렬 · 병합 정렬 · 퀵 정렬 · 힙 정렬 · 계수 정렬 · 기수 정렬 · 버킷 정렬 · 팀 정렬 · 인트로 정렬

정렬 순서를 정하는 입력

정렬 키 · 비교 함수 · 전순서 · 콜레이션 · 로케일

정렬 알고리즘을 가르는 성질

안정 정렬 · 제자리 정렬 · 적응 정렬 · 내부 정렬 · 외부 정렬

정렬 알고리즘의 비용을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 결정 트리 · 비교 정렬 하한 · 로그 함수

정렬된 순서를 밑천으로 삼는 연산

이진 탐색 · 중복 제거 · 병합 조인 · 상위 N 질의 · 선택 알고리즘 · 중앙값

정렬 알고리즘이 도는 자료구조

배열 · 연결 리스트 · 이진 힙 · 우선순위 큐 · 인덱스 · B-tree