정렬 알고리즘(Sorting algorithm)

정렬은 목록을 크기순으로 늘어놓는 일입니다. 컴퓨터가 하는 일 가운데 가장 흔한 것 중 하나이고, 정렬해 두면 이진 탐색⁠(binary search)⁠으로 빨리 찾고, 같은 것끼리 모으고, 중앙값⁠(median)⁠을 바로 읽을 수 있습니다. 방법은 수십 가지이지만, 두 원소⁠(element)⁠를 비교해 순서를 정하는 방법들은 비교 횟수로 비용을 잽니다.

알고리즘⁠(algorithm)⁠ , 입력 . 새로 섞기

참고로 n = 24일 때 $n^2/4 = 144$, $n \log_2 n \approx 110$입니다.

삽입 정렬⁠(insertion sort)⁠은 카드를 손에 쥐듯, 새 원소를 이미 정렬된 앞부분의 알맞은 자리까지 한 칸씩 밀어 넣습니다. 한 칸 밀 때마다 순서가 뒤바뀐 쌍(역순쌍⁠, inversion⁠) 하나가 풀립니다. 그래서 역순쌍이 I개이면 비교 횟수는 I 이상 $I + n - 1$ 이하입니다. 무작위 순열⁠(permutation)⁠에서는 두 원소가 뒤바뀌어 있을 확률⁠(probability)⁠이 1/2이니 역순쌍이 평균 $n(n-1)/4$개이고, 비교도 평균 $\Theta(n^2)$번입니다. 반면 역순쌍이 몇 개 없는 거의 정렬된 입력은 n번 남짓에 끝냅니다. 병합 정렬은 반으로 나눠 각각 정렬한 뒤 합치는 분할 정복⁠(divide and conquer)⁠입니다. 어떤 입력에서든 비교가 $n \log_2 n$번을 넘지 않고, 가장 운이 좋아도 그 절반쯤은 듭니다. 힙 정렬⁠(heapsort)⁠은 목록을 힙(가장 큰 값을 늘 맨 위에 두는 트리⁠(tree)⁠ 모양의 자료 구조)으로 만든 뒤 가장 큰 원소를 하나씩 꺼내 뒤에서부터 채웁니다. 최악의 경우에도 $O(n \log n)$이고 따로 큰 메모리가 필요 없지만, 비교 횟수는 병합 정렬의 두 배쯤입니다.

퀵정렬⁠(quicksort)⁠은 기준 원소(피벗⁠, pivot⁠)를 하나 골라 그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 가른 뒤 양쪽을 재귀⁠(recursion)⁠로 정렬합니다. 여기서는 구간의 마지막 원소를 피벗으로 씁니다. 무작위로 섞인 입력에서는 평균 비교 횟수가 n = 24일 때 약 93번이고, n이 커지면 $2n \ln n \approx 1.39\, n \log_2 n$에 비율이 1로 가까워집니다. 그러나 이미 정렬된 입력을 넣어 보세요. 피벗이 매번 가장 큰 원소라 한쪽이 텅 비고, $n(n-1)/2$번(n = 24이면 276번) 비교합니다. 피벗을 무작위로 고르면 늘 이렇게 느린 입력은 사라지고, 어떤 입력에서든 비교 횟수의 기댓값⁠(expected value)⁠이 무작위 입력의 평균과 같아집니다. 느린 실행은 운이 아주 나쁠 때만 남습니다(무작위 알고리즘⁠(randomized algorithm)⁠).

이보다 크게 나아질 수는 없습니다. 비교만 쓰는 정렬은 최악의 경우 적어도 $\log_2 n!$번 비교해야 합니다(비교 정렬의 하한⁠, comparison sorting lower bound⁠). 스털링 공식⁠(Stirling's formula)⁠으로 풀면 이 값은 $n \log_2 n - 1.44\,n$ 남짓이라, 첫째 항이 병합 정렬과 같습니다. 비용 말고 또 하나의 기준은 안정성입니다. 값이 같은 원소들의 원래 순서가 유지되면 안정 정렬⁠(stable sort)⁠이라 하는데, 삽입 정렬과 병합 정렬은 안정하고 퀵정렬과 힙 정렬은 보통 그렇지 않습니다.

이어지는 곳. 병합 정렬은 1945년 폰 노이만이, 퀵정렬은 1960년 무렵 영국의 컴퓨터 과학자 호어가 고안했고, 오늘날 프로그래밍 언어의 표준 정렬은 이들을 섞어 쓰는 경우가 많습니다. 퀵정렬의 평균 비교 횟수는 기댓값의 선형성(여러 수를 더한 것의 기댓값은 각 기댓값의 합이라는 성질)과 조화급수⁠(harmonic series)⁠로 계산합니다. 퀵정렬처럼 가르되 k번째 원소가 든 한쪽만 따라가면(퀵셀렉트⁠, quickselect⁠), 전부 정렬하지 않고도 k번째로 작은 원소를 평균 $O(n)$에 찾습니다. 기수 정렬⁠(radix sort)⁠은 원소끼리 비교하지 않습니다. 세 자리 수라면 일의 자리 숫자에 따라 0~9번 칸에 나눠 담았다가 순서대로 모으고, 십의 자리, 백의 자리로 같은 일을 되풀이합니다. 이때 한 칸 안에서는 들어온 순서를 그대로 지켜야 앞 단계에서 맞춰 둔 아랫자리 순서가 망가지지 않습니다. 비교 대신 진법⁠(positional notation)⁠의 자릿수를 이용하므로 비교 정렬의 하한을 비켜 가고, 자릿수 k가 정해져 있으면 $k(n + 10)$번 정도의 일로 끝납니다. 호어는 1971년 퀵셀렉트의 원형인 자기 프로그램 FIND가 옳다는 것을 반복 불변식⁠(loop invariant)⁠으로 증명해 보이기도 했는데, 이렇게 프로그램을 증명하는 규칙이 호어 논리⁠(Hoare logic)⁠입니다. 그 증명에서 '정렬한다'는 명세에는 출력이 정렬되어 있다는 것 말고도 출력이 입력을 재배열한 것이라는 조건이 들어가야 합니다. 빠뜨리면 빈 배열을 돌려주는 프로그램도 '증명'되기 때문입니다.