줄 세우기의 한계

카드 천 장을 가장 빨리 줄 세우는 방법은? 인구조사의 천공 카드⁠(punched card)⁠에서 퀵정렬⁠(quicksort)⁠까지, 그리고 어떤 방법도 넘을 수 없는 n log n의 벽.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 알고리즘⁠(algorithm)⁠ 그림 아래의 ◀ ▶ 단추나 막대로 한 걸음씩 앞뒤로 오갈 수 있고, 걸음마다 무슨 일이 일어났는지 한 줄 설명이 붙습니다. 그림 속 점과 나뭇잎은 끌거나 누를 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

번호가 적힌 카드 천 장이 뒤섞여 있다고 해 봅시다. 이것을 번호 차례로 줄 세워야 합니다. 도구는 하나뿐입니다. 카드 두 장을 집어 어느 쪽 번호가 작은지 보고 앞뒤를 정하는 것입니다. 이 비교를 한 번 하는 데 1초가 걸린다면, 다 세우는 데 얼마나 걸릴까요?

가장 먼저 떠오르는 방법으로는 수십만 번을 비교하게 됩니다. 쉬지 않고 해도 며칠이 걸립니다. 조금 영리한 방법으로는 9천 번이 채 안 됩니다. 두 시간 반이면 끝납니다. 그렇다면 더 영리한 방법으로 천 번, 백 번까지 줄일 수 있을까요? 이 글의 답은 '아니오'입니다. 비교만 쓰는 방법이라면, 운 좋은 배열이 아니라 가장 나쁜 배열을 만났을 때 적어도 8,530번은 해야 합니다. 이것은 지금까지 나온 방법들의 기록이 아니라, 앞으로 누가 발명할 어떤 방법도 넘을 수 없는 벽입니다.

줄 세우기는 오래된 일입니다. 교사이자 목사였던 로버트 코드리가 1604년 런던에서 펴낸 『알파벳 순 표』는 흔히 최초의 영어 단일어 사전으로 꼽힙니다. 코드리는 머리말에서 독자에게 이 책을 제대로 이용하려면 먼저 알파벳의 차례를 책을 보지 않고도 알 만큼 익혀 두라고 일러두었습니다. 낱말을 글자 차례로 늘어놓는다는 발상이 아직 당연하지 않던 때였습니다. 그 뒤로 사전과 전화번호부, 도서관의 카드 목록, 우체국의 분류함, 그리고 컴퓨터의 데이터베이스가 모두 정렬 위에 섰습니다.

이 글은 세 가지를 묻습니다. 줄 세우기는 얼마나 빨라질 수 있는가? 그 한계를 어떻게 증명할 수 있는가? 그리고 그 한계를 비껴가는 길은 없는가? 이야기는 두 카드를 한 번도 비교하지 않고 6천만 명이 넘는 인구를 센 기계에서 시작합니다.

1 · 1890년의 인구조사구멍 뚫린 카드로 센 나라

이 절은 이야기로 시작합니다. 수천만 장의 카드를 기계로 세고 나누던 시대에, 줄 세우기는 어떤 일이었을까? 여기서 나오는 '비교하지 않는 분류기'는 7절에서 이 글의 결론을 비껴가는 열쇠가 됩니다.

미국 헌법은 10년마다 인구를 세어 각 주의 하원 의석을 나누도록 정해 두었습니다. 첫 조사는 1790년이었습니다. 19세기 후반 유럽에서 이민이 몰려들자 조사는 점점 버거워졌습니다. 1880년 조사에서는 수많은 사무원이 조사표를 넘기며 집계표의 칸에 금을 그어 세었고, 최종 집계를 마치는 데 8년 가까이 걸렸습니다. 이대로라면 1890년 조사의 결과는 1900년 조사가 시작될 때까지도 다 나오지 않을 판이었습니다.

1880년 조사에서 일했던 젊은 공학자 허먼 홀러리스는 사람마다 카드를 한 장씩 만들자고 생각했습니다. 그의 회고에 따르면 서부를 여행할 때 받은 기차표가 실마리였습니다. 차장은 '펀치 사진'이라 불리던 그 표에 구멍을 뚫어 승객의 머리색, 눈 색, 코의 크기 같은 인상착의를 적었습니다. 홀러리스는 인구조사도 사람마다 펀치 사진을 한 장씩 만들면 된다고 여겼습니다. 성별, 나이, 태어난 곳, 직업이 카드의 정해진 자리에 뚫린 구멍이 됩니다.

그의 집계기⁠(tabulating machine)⁠는 카드를 판 위에 놓고 핀이 달린 뚜껑을 내리누르는 기계였습니다. 구멍이 있는 자리에서는 핀이 수은이 든 작은 컵까지 내려가 전기가 통했고, 그 전류가 해당하는 계수기의 바늘을 한 칸 돌렸습니다. 같은 전류가 옆에 놓인 분류 상자의 뚜껑 하나를 열었습니다. 사무원은 열린 칸에 카드를 넣기만 하면 되었습니다. 이 기계는 경쟁 시험을 거쳐 1890년 조사에 채택되었고, 6천2백만 명이 넘는 인구의 첫 집계는 몇 주 만에 나왔다고 전합니다.

곧 다른 나라들도 이 기계를 빌렸습니다. 1890년 오스트리아, 1891년 캐나다, 1897년 러시아 제국의 첫 전국 인구조사가 이 기계로 집계되었다고 전합니다. 홀러리스는 1896년 집계기 회사를 세웠고, 이 회사는 1911년 합병을 거쳐 1924년 IBM이라는 이름을 얻었습니다. 20세기 전반의 '정보 처리'란 대부분 이런 천공 카드를 세고, 나누고, 줄 세우는 일이었습니다.

워싱턴에서 출발한 집계 기계가 대서양을 건너간 길입니다. 인구조사는 나라가 국민을 세는 일이었고, 집계기는 그 일을 빠르게 만든 첫 정보 기계였습니다. 선이나 점에 마우스를 올리면 설명이 나옵니다.

카드를 줄 세우는 기계도 따로 나왔습니다. 20세기 초의 카드 분류기⁠(card sorter)⁠는 카드 뭉치를 빠르게 넘기며 한 번에 한 열만 읽고, 그 열에 뚫린 숫자에 따라 카드를 0번부터 9번까지의 칸 가운데 하나로 떨어뜨렸습니다. 여기서 눈여겨볼 점이 있습니다. 이 기계는 두 카드를 서로 비교하지 않습니다. 카드 한 장만 보고 곧바로 갈 곳을 정합니다. 이 차이가 얼마나 중요한지는 7절에서 드러납니다. 그 전에, 사람이 손으로 하는 줄 세우기부터 따져 봅시다.

사람의 손으로 하는 분류도 거대한 산업이었습니다. 1876년 미국 애머스트 칼리지의 사서 멜빌 듀이는 모든 책을 주제에 따라 000부터 999까지의 번호로 나누는 십진분류법을 펴냈고, 도서관의 카드 목록은 이런 번호와 알파벳 순서로 줄 세운 서랍이 되었습니다. 우체국 직원들은 벽을 가득 채운 칸막이 분류함 앞에서 편지를 행선지별로 던져 넣었습니다.

글자 차례로 줄 세우는 일 자체도 누군가 고안한 방법이었습니다. 기원전 3세기 이집트 알렉산드리아의 도서관에서 학자 칼리마코스가 엮은 목록 『피나케스』는 분야마다 저자 이름의 첫 글자 순서로 두루마리를 정리했다고 전합니다. 지중해 곳곳에서 모아들인 책을 찾으려면, 내용을 몰라도 누구나 따를 수 있는 순서가 필요했던 것입니다(알렉산드리아 무세이온). 그런데 중세 유럽의 학자들은 이 순서를 오랫동안 꺼렸습니다. 지식은 신학의 차례나 주제의 차례처럼 뜻에 따라 늘어놓아야 한다고 여겼고, 글자 차례는 뜻과 아무 상관이 없는 순서였기 때문입니다. 12–13세기에 설교자들이 성경의 낱말을 찾아보려고 알파벳 순 도구를 쓰기 시작했고, 파리의 도미니코회 수사들이 성경 낱말 색인을 그렇게 엮으면서 이 순서가 자리를 잡았습니다. 기억에 기대던 학문이 책을 찾아보는 학문으로 옮겨 가는 길목이었습니다. 뜻에 따른 순서와 글자에 따른 순서 사이의 이 긴장은 듀이의 분류법에도 남아 있습니다. 서가는 주제로 나누고, 같은 주제 안에서는 다시 번호와 알파벳으로 줄을 세웁니다.

2 · 손안의 카드삽입 정렬⁠(insertion sort)⁠과 비교 세기

카드놀이를 하는 사람은 손에 든 카드를 대개 이렇게 정리합니다. 이미 정리된 카드들 옆에 새 카드를 하나 가져와, 그보다 큰 카드를 지나 왼쪽으로 밀어 넣습니다. 제자리를 찾으면 멈추고 다음 카드를 가져옵니다. 이 방법이 삽입 정렬입니다. 유한한 걸음 안에 반드시 끝나는 분명한 절차이니 알고리즘이고, 목록을 차례대로 늘어놓는 여러 정렬 알고리즘⁠(sorting algorithm)⁠ 가운데 가장 손에 익은 것입니다.

이 절의 물음은 이것입니다. 이 손쉬운 방법은 카드 $n$장에 비교를 몇 번 할까? 네 장으로 먼저 따라가 봅시다. 손에 3, 1, 4, 2가 있습니다. 1을 가져와 3과 비교하고 앞으로 넣으면 1, 3. 4를 가져와 3과 비교하면 이미 크니 그 자리에 둡니다(1, 3, 4). 2를 가져와 4, 3, 1과 차례로 비교해 1 뒤에 넣으면 1, 2, 3, 4입니다. 비교는 1 + 1 + 3 = 5번이었습니다.

빠르기를 재려면 무엇을 셀지 정해야 합니다. 기계마다, 사람마다 손 빠르기가 다르니 초를 세는 대신 비교 횟수를 셉시다. "이 카드가 저 카드보다 작은가?"라는 질문 하나가 한 번입니다. 아래 그림에서 카드 장을 순서로 놓고 한 걸음씩 돌려 보세요. 막대의 높이가 카드의 번호입니다.

새로 섞기 지금까지 비교 번입니다.

최악은 거꾸로 된 순서입니다. 두 번째 카드는 1번, 세 번째 카드는 2번, 마지막 카드는 $n-1$번 비교하니 모두

번입니다. 오른쪽 식은 앞뒤를 짝지어 더하면 보입니다. 다섯 장이면 1 + 2 + 3 + 4에서 1 + 4와 2 + 3이 모두 5이니 합은 5 × 4 ÷ 2 = 10입니다. 일반적으로는 합을 한 번은 앞에서부터, 한 번은 뒤에서부터 적어 위아래로 더합니다. 1과 $n-1$, 2와 $n-2$, …처럼 위아래 짝마다 합이 $n$이고 짝이 $n-1$개이니 합의 두 배가 $n(n-1)$입니다. 지금 카드 수로는 번입니다. 이 수는 $n$장 가운데 두 장을 고르는 방법의 수 $\binom{n}{2}$와 같습니다(이항계수⁠, binomial coefficient⁠). 거꾸로 된 순서에서는 모든 쌍을 한 번씩 비교하는 셈입니다.

자리바꿈 횟수에는 더 깔끔한 규칙이 있습니다. 앞에 있는 카드가 뒤의 카드보다 큰 쌍을 '뒤집힌 쌍⁠(inversion)⁠'이라고 부릅시다. 3, 1, 4, 2에서는 (3, 1), (3, 2), (4, 2)의 세 쌍이 뒤집혀 있습니다. 순서가 뒤집힌 이웃한 두 카드를 바꾸면, 다른 카드들과의 관계는 그대로이고 그 두 카드 사이의 뒤집힘만 풀리므로 뒤집힌 쌍이 정확히 하나 줄어듭니다. 삽입 정렬은 새 카드를 한 칸씩 왼쪽으로 밀 때마다 바로 이런 바꿈을 합니다. 그러니 삽입 정렬의 자리바꿈 횟수는 처음 배열의 뒤집힌 쌍의 수와 같고(3, 1, 4, 2에서는 1이 한 칸, 2가 두 칸 움직여 3번), 지금 입력에서는 개입니다.

무작위로 섞으면 어떤 두 카드든 앞뒤가 뒤집혀 있을 확률⁠(probability)⁠이 절반입니다. 쌍은 $n(n-1)/2$개이니 뒤집힌 쌍의 평균⁠(mean)⁠은 그 절반인 $n(n-1)/4$, 대략 $n^2/4$입니다. 이웃한 둘을 바꿀 때마다 뒤집힌 쌍의 수가 정확히 하나씩 변한다는 이 성질은 다른 증명의 열쇠이기도 합니다. 1880년 미국을 휩쓴 열다섯 조각 퍼즐에서, 배치의 절반은 아무리 밀어도 풀리지 않는다는 증명입니다(「불가능의 증명」 2절).

이것이 얼마나 큰지 봅시다. 카드 천 장이면 평균 25만 번, 최악 499,500번입니다. 1초에 한 번씩 비교하면 평균으로도 사흘쯤 걸립니다. 1890년의 인구 6천2백만 명을 삽입 정렬로 줄 세운다면 1초에 10억 번 비교하는 오늘의 컴퓨터로도 열흘이 넘게 걸립니다. 문제는 모든 쌍을 비교한다는 데 있습니다. 카드가 두 배가 되면 쌍은 네 배가 됩니다. 모든 쌍을 보지 않고도 줄을 세울 수 있을까요? 정리하면, 삽입 정렬은 뒤집힌 쌍을 하나씩 풀기 때문에 평균 $n^2/4$번쯤 일하고, 카드가 늘면 그 제곱으로 느려집니다.

3 · 반으로 나누기폰 노이만의 병합 정렬⁠(merge sort)⁠과 n log n

1945년 필라델피아의 무어 스쿨에서는 그곳에서 만든 전자식 계산기 ENIAC의 후속 기계 EDVAC의 설계가 한창이었습니다. 프로그램을 자료와 같은 기억 장치에 넣는다는 저장 프로그램⁠(stored program)⁠의 구상은 「기계가 풀 수 없는 문제」 6절에 있습니다. 그해 존 폰 노이만은 이 기계를 위한 프로그램 하나를 손으로 적었습니다. 숫자 계산이 아니라 정렬, 정확히는 이미 정렬된 두 목록을 하나로 합치는 병합이었습니다. 천공 카드 분류기와 병합기가 하던 일을 새 기계가 얼마나 잘 해낼지 가늠해 보려 한 것으로 보입니다. 1970년 스탠퍼드의 컴퓨터 과학자 도널드 크누스는 이 원고를 찾아 분석하고, 저장 프로그램 컴퓨터⁠(stored-program computer)⁠를 위해 쓰인 가장 이른 프로그램 가운데 하나로 소개했습니다. 폰 노이만이 그보다 앞선 1928년 괴팅겐에서 게임의 최소최대 정리⁠(minimax theorem)⁠를 증명한 이야기는 「이기는 쪽이 존재한다」 5절에 있습니다.

이 절의 물음은 이것입니다. 모든 쌍을 비교하지 않고 줄을 세우려면 어떻게 해야 할까? 폰 노이만의 답은 '반으로 나누고, 합치기'였습니다.

병합의 핵심은 간단합니다. 정렬된 카드 더미 두 개가 있으면 두 더미의 맨 위 카드만 보면 됩니다. 둘 중 작은 쪽을 집어 새 더미에 올리고, 다시 두 맨 위 카드를 비교합니다. 예를 들어 2, 5, 8과 3, 4, 9를 합치면, 2와 3을 비교해 2, 5와 3을 비교해 3, 5와 4를 비교해 4, 5와 9를 비교해 5, 8과 9를 비교해 8을 차례로 집고, 남은 9는 비교 없이 올립니다. 여섯 장에 비교 다섯 번입니다. 비교 한 번마다 카드 한 장이 제자리로 가고 마지막 한 장은 비교가 필요 없으니, 모두 $m$장을 합치는 데 비교는 많아야 $m-1$번입니다.

그러면 정렬은 이렇게 됩니다. 더미를 반으로 나누고, 각 반을 같은 방법으로 정렬한 다음, 둘을 병합합니다. 문제를 같은 모양의 더 작은 문제로 줄이는 이 방식을 재귀⁠(recursion)⁠라 하고, 반으로 나눠 풀고 답을 합치는 틀을 분할 정복⁠(divide and conquer)⁠이라고 부릅니다.

재귀를 끝까지 풀면 카드는 결국 한 장씩으로 나뉩니다. 한 장짜리 더미는 이미 정렬되어 있습니다. 그다음부터는 병합만 남습니다. 아래 그림은 카드 장에서 이 과정을 아래로 쌓아 가며 보여 줍니다. 맨 윗줄은 한 장씩의 더미, 그 아래 줄은 두 장씩, 네 장씩으로 병합된 더미입니다.

▶ 한 줄 끝까지 새로 섞기

줄마다 모든 카드가 한 번씩 새 더미로 옮겨 가므로, 한 줄에서 하는 비교는 많아야 카드 수 $n$입니다. 줄의 수는 몇 번 반으로 나눠야 한 장이 되는가입니다. 16장이면 16 → 8 → 4 → 2 → 1로 네 번이니 4줄입니다. 이 수를 $\log_2 n$('로그 2의 n')으로 적습니다. 2를 몇 번 곱해야 $n$이 되는가와 같은 수이고($2^4 = 16$), $n$이 2의 거듭제곱이 아니면 정수⁠(integer)⁠가 아닌 값이 됩니다($\log_2 1000 \approx 9.97$). 그러니 전체 비교는 많아야

입니다. 지금 카드 수로는 번이고, 방금 실제로 한 비교는 번입니다. 같은 이야기를 식으로 적을 수도 있습니다. $n$장을 정렬하는 비교 횟수를 $T(n)$이라 하면, 반씩 정렬하는 데 $2T(n/2)$, 병합에 많아야 $n$이 드니 $T(n) \le 2T(n/2) + n$입니다. 작은 경우의 답으로 큰 경우를 적는 이런 식이 점화식⁠(recurrence relation)⁠이고, $T(n) \le n\log_2 n$이 모든 2의 거듭제곱에서 성립한다는 것은 수학적 귀납법⁠(mathematical induction)⁠으로 한 줄에 증명됩니다. 한 장이면 비교가 필요 없으니 $T(1) = 0 = 1 \cdot \log_2 1$이고, $n/2$장에서 맞다면 $\log_2(n/2) = \log_2 n - 1$이므로

로그가 등장한 까닭은 '반으로 나누기를 몇 번 하는가'를 셌기 때문입니다. 차이는 매우 큽니다. 카드 천 장을 병합 정렬하면 비교는 많아야 8,977번입니다. 삽입 정렬의 최악 499,500번의 50분의 1도 안 됩니다. 로그는 원래 1614년 스코틀랜드의 수학자 존 네이피어가 곱셈을 덧셈으로 바꾸어 천문 계산의 수고를 덜려고 내놓은 것입니다. 알고리즘에서는 거꾸로, 곱이 아니라 '되풀이된 절반'을 세는 도구가 되었습니다. 로그표가 급수⁠(series)⁠와 함께 자란 이야기는 「한 점에서 전부를」 6절에 있습니다.

병합 정렬에는 또 하나의 장점이 있었습니다. 더미의 맨 위만 보면 되므로, 앞에서부터 차례로만 읽을 수 있는 자기 테이프⁠(magnetic tape)⁠에 꼭 맞았습니다. 1950–60년대 기업의 컴퓨터실에서 테이프 드라이브 여러 대를 오가며 급여 명부와 재고 목록을 병합하는 일은 컴퓨터가 하는 가장 흔한 일이었습니다. 크누스의 기록에 따르면, 1960년대 컴퓨터 제조사들은 고객 전체를 통틀어 컴퓨터 가동 시간 가운데 25%가 넘는 몫이 정렬에 쓰인다고 추정했습니다.

정렬이 그만큼 흔했기에 정렬 프로그램을 매번 손으로 짜는 대신 기계에게 짜게 하려는 시도도 일찍 나왔습니다. ENIAC의 첫 프로그래머 가운데 한 사람인 베티 홀버턴은 1950년대 초 UNIVAC을 위해 '정렬–병합 생성기'를 짰습니다. 자료의 형식과 정렬 기준을 적어 넣으면 그 자료에 맞는 정렬·병합 프로그램을 만들어 내는 프로그램입니다. 동료 그레이스 호퍼는 뒤에 이것을 컴퓨터로 프로그램을 쓴 첫 사례로 꼽았습니다.

이제 '빠르다'를 말하는 방법이 필요합니다. $n^2/4$와 $n\log_2 n$을 비교할 때 앞의 $1/4$ 같은 상수는 기계가 빨라지면 바뀝니다. 바뀌지 않는 것은 $n$이 커질 때 자라는 모양입니다. $n^2$ 꼴은 카드가 두 배가 되면 일이 네 배가 되고, $n\log_2 n$ 꼴은 두 배를 조금 넘을 뿐입니다. 그래서 상수배를 무시하고 모양만 적는 점근 표기법⁠(asymptotic notation)⁠을 씁니다. 삽입 정렬은 $O(n^2)$('빅오 n 제곱'), 병합 정렬은 $O(n\log n)$입니다. $O(g)$는 '$n$이 충분히 크면 $g$의 어떤 상수배를 넘지 않는 양'이라는 뜻입니다. $\log n$의 밑을 적지 않는 것은 밑을 바꾸면 상수배만 달라지기 때문입니다.

이 표기는 알고리즘보다 먼저 정수론⁠(number theory)⁠에서 태어났습니다. 1894년 독일의 수학자 파울 바흐만이 '이것의 상수배를 넘지 않는 양'을 $O$로 적었고, 1909년 괴팅겐의 수학자 에드문트 란다우가 소수 정리⁠(prime number theorem)⁠의 오차를 다루는 책에서 이 기호를 두루 쓰며 퍼뜨렸습니다. 소수 정리가 무엇을 말하는지는 「소수를 세는 사람들」에 있습니다. 1976년 크누스는 알고리즘 연구자들에게 보낸 글에서 $O$와 함께 $\Omega$('오메가'), $\Theta$('세타') 두 기호를 쓰자고 제안했고, 이것이 오늘날의 표준이 되었습니다. $\Omega(g)$는 아래쪽 한계, 곧 '$n$이 충분히 크면 $g$의 어떤 양의 상수배보다 작아지지 않는 양'이고, $\Theta(g)$는 위아래를 모두 묶은 것, 곧 '$g$의 두 상수배 사이에 끼는 양'입니다. 예를 들어 $n^2/4$는 $\Theta(n^2)$입니다.

모양의 차이는 멀리서 볼수록 커집니다. 아래 그림의 가로축은 $n =$ 까지입니다. 이 끝을 (10의 거듭제곱 지수)로 늘려 멀리서 보세요. 세로축은 늘 n log₂ n이 화면의 4분의 3쯤에 오도록 맞춰집니다.

가로축을 넓힐수록 n²은 화면을 뚫고 올라가 거의 세로줄이 되고, n log₂ n과 n은 거의 같은 모양의 직선이 됩니다. 두 직선의 차이는 $\log_2 n$배뿐이고, 로그는 아주 느리게 자랍니다. 노란 점의 $n =$ 에서 $n^2$은 , $n\log_2 n$은 이고, 둘은 배 차이가 납니다. 1초에 10억 번 비교하는 컴퓨터라면 평균 $n^2/4$번의 삽입 정렬은 , 병합 정렬은 입니다. 점을 오른쪽 끝까지 끌고 지수를 6(백만 장)까지 올려 보세요.

4 · 모스크바의 사전호어의 퀵정렬과 무작위의 힘

이 절의 물음은 이것입니다. 나누기를 영리하게 하면 합치기를 없앨 수 있을까? 그리고 운 나쁜 입력을 만나 느려지는 일을 동전 던지기로 막을 수 있을까?

1959년 가을, 옥스퍼드에서 고전학과 철학을 공부한 스물다섯 살의 영국인 토니 호어가 영국 문화원의 교환 학생으로 모스크바 대학에 왔습니다. 그는 군 복무 중 러시아어를 배웠고, 모스크바에서는 확률론의 대가 안드레이 콜모고로프의 학파에서 공부했습니다. 훗날 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠에 이름을 남긴 바로 그 콜모고로프입니다. 호어는 그곳에서 기계 번역⁠(machine translation)⁠에도 손을 댔습니다. 1954년 뉴욕의 조지타운–IBM 시연 이후 미국과 소련은 서로의 과학 문헌을 기계로 읽으려 경쟁하고 있었습니다(「말을 세는 기계」 7절).

러시아어 문장을 영어로 옮기려면 낱말마다 사전을 찾아야 합니다. 그런데 사전은 자기 테이프에 알파벳 순서로 들어 있었고, 테이프는 앞에서부터 차례로만 읽을 수 있었습니다. 낱말을 나오는 순서대로 찾으면 테이프를 수없이 감았다 풀어야 합니다. 문장의 낱말을 먼저 알파벳 순으로 정렬해 두면 테이프를 한 번만 훑으며 모두 찾을 수 있습니다. 호어가 떠올린 정렬 방법은 이랬습니다. 낱말 하나를 기준(피벗⁠, pivot⁠)으로 골라, 그보다 앞서는 낱말은 왼쪽으로, 뒤에 오는 낱말은 오른쪽으로 가릅니다. 그리고 양쪽을 같은 방법으로 정렬합니다. 수로 해 보면, 5, 2, 8, 1, 9, 3에서 5를 피벗으로 고르면 나머지 다섯 수를 5와 한 번씩 비교해 왼쪽 2, 1, 3과 오른쪽 8, 9로 가릅니다. 왼쪽과 오른쪽을 따로 정렬해 1, 2, 3과 8, 9를 얻으면, 그 사이에 5를 두기만 하면 1, 2, 3, 5, 8, 9로 끝입니다. 병합 정렬은 나누기는 쉽고 합치기에서 일을 했지만, 퀵정렬은 나누기에서 일을 하고 합치기는 할 것이 없습니다.

이듬해 런던의 컴퓨터 회사 엘리엇 브라더스에 들어간 호어는 미국의 컴퓨터 과학자 도널드 셸이 막 발표한 빠른 정렬법(셸 정렬⁠, Shellsort⁠)을 구현하라는 일을 받았습니다. 1980년 컴퓨터 과학에서 가장 권위 있는 상인 튜링상⁠(Turing Award)⁠을 받으며 한 강연에서 호어가 회고한 바에 따르면, 그는 대개는 그보다 빠른 방법을 안다고 조심스럽게 말했고, 상사는 그럴 리 없다며 6펜스를 걸었습니다. 호어는 내기에서 이겼습니다. 다만 그는 이 방법을 깔끔하게 적을 말을 찾지 못해 애먹었고, 자기 자신을 부르는 프로시저, 곧 재귀를 허용한 새 언어 알골 60을 배우고서야 쉽게 적을 수 있었다고 회고했습니다. 1961년 미국 컴퓨터 학회(ACM)의 학술지 『ACM 통신』에 실린 '알고리즘 64: 퀵정렬'은 몇 줄짜리 알골 프로그램이었습니다.

아래에서는 같은 카드 장을 순서로 놓고 세 방법을 경주시킵니다. 시계는 초가 아니라 비교 횟수로 갑니다. 세 정렬이 모두 한 번 비교할 때마다 한 칸씩 나아갑니다. 퀵정렬의 피벗은 입니다.

▶ 경주 시작 처음으로 새로 섞기 지금까지 비교 번. 끝까지 가면 삽입 번, 병합 번, 퀵 번입니다. 참고로 $n\log_2 n$은 입니다.

퀵정렬이 느려진 까닭은 피벗에 있습니다. 이미 정렬된 카드에서 맨 앞 카드는 가장 작은 카드입니다. 그것을 기준으로 가르면 왼쪽은 비고 오른쪽에 나머지 전부가 남습니다. 한 번 가를 때마다 한 장씩만 줄어드니 비교는 $(n-1) + (n-2) + \cdots + 1 = n(n-1)/2$번, 삽입 정렬의 최악과 같습니다. 이상적인 피벗은 카드들의 한가운데 값, 곧 중앙값⁠(median)⁠입니다. 그러면 매번 정확히 반씩 갈라져 병합 정렬처럼 $\log_2 n$층이면 끝납니다.

중앙값을 찾는 데 드는 수고를 피하는 영리한 방법은 피벗을 무작위로 고르는 것입니다. 이렇게 동전 던지기를 계산에 섞는 방법을 무작위 알고리즘⁠(randomized algorithm)⁠이라고 합니다. 그러면 평균 비교 횟수, 곧 같은 입력으로 여러 번 돌렸을 때의 평균(기댓값⁠, expected value⁠)은 얼마일까요? 계산은 뜻밖에 간단합니다.

퀵정렬에서 비교는 언제나 피벗과 다른 카드 사이에서만 일어납니다. 크기 순으로 1번부터 5번까지의 카드가 있다고 하고, 2번과 4번이 서로 비교될지 봅시다. 둘 사이의 카드 2, 3, 4 가운데 3번이 먼저 피벗으로 뽑히면, 2번은 왼쪽, 4번은 오른쪽으로 갈라져 영영 만나지 않습니다. 2번이나 4번이 먼저 뽑히면 그 피벗이 다른 하나와 비교됩니다. 1번이나 5번이 먼저 뽑히는 것은 세 카드를 갈라놓지 않으니 상관없습니다. 그러니 둘이 비교될 확률은 세 장 가운데 두 장, 곧 2/3입니다.

일반적으로 크기 순으로 $i$번째와 $j$번째인 두 카드가 서로 비교되는 것은, 그 사이의 $j-i+1$장 가운데 둘 중 하나가 가장 먼저 피벗으로 뽑힐 때뿐입니다. 사이의 다른 카드가 먼저 뽑히면 둘은 서로 다른 쪽으로 갈라져 영영 만나지 않습니다. 그러니 두 카드가 비교될 확률은 $2/(j-i+1)$입니다. 쌍마다 '비교되면 1, 아니면 0'을 세어 모두 더한 것이 비교 횟수이고, 합의 평균은 평균의 합이므로 확률들을 모든 쌍에 대해 더하면 됩니다(Σ는 모든 쌍 $i \lt j$에 대해 더하라는 뜻입니다).

입니다. 괄호 안은 조화급수⁠(harmonic series)⁠의 앞부분이고, 이것은 $\ln n$처럼 느리게 자랍니다. $\ln n$은 자연로그⁠(natural logarithm)⁠, 곧 약 2.718인 수 $e$를 몇 번 곱해야 $n$이 되는가를 나타내는 수로, $\log_2 n$의 약 0.69배입니다. 그래서 $2n\ln n \approx 2 \times 0.69 \times n\log_2 n \approx 1.39\,n\log_2 n$입니다. 뒤의 두 $\approx$는 $n$이 클 때 비율이 1로 다가간다는 뜻이고, 카드가 적을 때는 $-4n$ 같은 항 때문에 실제 평균이 $2n\ln n$보다 꽤 작습니다. 지금 카드 수에서 이 평균을 정확히 계산해 반올림하면 번입니다.

$n$이 아주 크면 병합 정렬보다 비교가 40%쯤 많아집니다(천 장이면 평균 약 1만 1천 번으로 25%쯤 많습니다). 그래도 퀵정렬은 카드를 옮기는 일이 적고 따로 담을 공간이 거의 필요 없어 실제로는 흔히 더 빠릅니다.

중요한 것은 이 평균이 (번호가 모두 다르기만 하면) 입력과 상관없이 성립한다는 점입니다. 운은 자료가 아니라 알고리즘 쪽에 있습니다. 어떤 심술궂은 입력을 넣어도, 느려질 확률은 우리가 던진 동전이 연달아 나쁘게 나올 확률뿐입니다. 흔히 '무작위 퀵정렬은 입력이 무작위일 때 빠르다'고 생각하지만, 그것은 맨 앞 원소를 피벗으로 쓰는 퀵정렬의 이야기입니다. 무작위 피벗은 입력이 무엇이든 평균이 같습니다.

단, 이 보장에는 입력이 동전을 던지기 전에 정해져 있다는 조건이 붙습니다. 1999년, 벨 연구소에서 오래 일한 더글러스 매킬로이는 「퀵정렬을 죽이는 적수」라는 짧은 글에서 특별한 비교 함수⁠(function)⁠를 만들었습니다. 이 함수는 값을 미리 정해 두지 않고, 정렬이 비교를 물을 때마다 앞의 답들과 어긋나지 않는 범위에서 가장 곤란한 답을 그때그때 지어냅니다. 이 적수는 널리 쓰이던 C 언어 표준 라이브러리(언어에 딸려 오는 기본 도구 모음)의 퀵정렬을 제곱 시간으로 끌어내렸습니다. 답이 끝까지 서로 어긋나지 않으니, 결과적으로 그런 입력이 처음부터 있었던 셈입니다. 이렇게 알고리즘이 한 수 두면 적수가 받아 두는 관점은 6절의 하한⁠(lower bound)⁠ 증명에서 다시 쓰입니다.

최악에도 $n\log n$을 지키면서 따로 담을 공간도 쓰지 않는 방법은 1964년에 나왔습니다. 영국의 컴퓨터 과학자 J. W. J. 윌리엄스의 힙 정렬입니다. 힙⁠(heap)⁠은 부모가 언제나 자식보다 작도록 카드를 이진 트리(맨 위의 뿌리에서 시작해 마디마다 아래로 가지가 많아야 둘씩 갈라지는 구조)에 담은 구조로, 가장 작은 카드가 늘 뿌리에 있습니다. 뿌리를 꺼내고 트리⁠(tree)⁠를 다시 맞추는 데는 층마다 비교 두 번, 모두 $2\log_2 n$번 남짓이면 되니, $n$번 꺼내면 정렬이 끝납니다. 같은 해 미국의 컴퓨터 과학자 로버트 플로이드가 힙을 더 빨리 쌓는 방법을 보탰습니다. '가장 급한 것부터 꺼내 주는' 이 구조를 우선순위 큐⁠(priority queue)⁠라고 부르며, 지도에서 최단 경로⁠(shortest path)⁠를 찾는 다익스트라 알고리즘⁠(Dijkstra's algorithm)⁠의 엔진이기도 합니다(「일곱 다리의 도시」 5절).

힙은 토너먼트와 닮았습니다. 두 명씩 겨뤄 이긴 쪽이 올라가면 뿌리에는 챔피언이 남습니다. 1883년 옥스퍼드의 수학 강사 찰스 도지슨, 곧 루이스 캐럴은 녹다운 방식의 테니스 대회가 2등 상을 엉뚱한 사람에게 준다고 비판하는 소책자를 냈습니다. 진짜 2등은 첫 판에 1등을 만나 떨어졌을 수도 있으니까요. 다만 진짜 2등은 1등에게 직접 진 선수들 가운데 있으므로, 그들끼리만 다시 겨루면 됩니다. 힙에서도 다음 챔피언은 늘 뿌리 바로 아래에 있어서, 힙 정렬⁠(heapsort)⁠은 뿌리를 꺼낸 뒤 그 근처에서부터 다시 겨루게 합니다. 오늘날 프로그래밍 언어 C++에 딸린 표준 도구 모음(표준 라이브러리)의 정렬은 흔히 퀵정렬로 달리다가 재귀가 너무 깊어지면 힙 정렬로 갈아타는 혼합 방식을 씁니다.

5 · 스무 고개정렬해 두면 찾기가 쉽다

이 절의 물음은 둘입니다. 왜 이렇게까지 줄을 세울까? 그리고 예·아니오 질문으로 무언가를 찾을 때 질문은 최소 몇 번 필요할까? 둘째 물음의 답이 6절의 벽이 됩니다. 첫째 물음의 답은 줄 선 목록에서는 찾기가 빠르기 때문입니다. 두꺼운 사전에서 낱말을 찾을 때 첫 쪽부터 넘기는 사람은 없습니다. 가운데쯤을 펼쳐 찾는 낱말이 앞쪽인지 뒤쪽인지 보고, 남은 절반에서 다시 가운데를 펼칩니다. 이것이 이진 탐색⁠(binary search)⁠입니다. 아래 놀이에서 직접 해 보세요. 1부터 사이에 수 하나가 숨어 있습니다. 분홍 점을 끌어 수를 고르고 물으면 숨은 수가 그보다 큰지 작은지 알려 줍니다.

이 수로 묻기 가운데를 골라 묻기 새 놀이 지금 고른 수는 , 지금까지 한 질문은 번입니다.

'가운데를 골라 묻기'만 누르면 몇 번 만에 찾나요? 한 번 물을 때마다 남은 후보가 절반 이하로 줄어듭니다. $k$번 물으면 $N/2^k$개 이하가 남으니, 후보가 $N$개일 때 필요한 질문은 많아야 $\lceil \log_2 (N+1) \rceil$번($\lceil\;\rceil$는 소수점 아래를 올려 정수로 만든다는 뜻입니다. 예를 들어 $\log_2 101 \approx 6.66$을 올리면 7), 지금은 번입니다. 100개면 7번, 천 개면 10번, 백만 개면 20번입니다. 예·아니오로 답하는 스무 고개로 백만 가지 가운데 하나를 맞힐 수 있는 까닭이 여기에 있습니다. 반대로 한가운데가 아닌 곳을 물으면 운이 나쁠 때 큰 쪽이 남습니다. 끝 쪽만 골라 물어 보세요. 최악의 경우를 가장 적게 하려면 매번 반에 가깝게 갈라야 합니다.

이 생각은 오래되었지만 제대로 적기는 뜻밖에 어려웠습니다. 크누스에 따르면 이진 탐색은 1946년 ENIAC을 만든 존 모클리가 무어 스쿨 강의에서 처음 언급했지만, 목록의 크기가 무엇이든 올바르게 작동하는 판은 1960년에야 출판되었습니다. 1980년대 벨 연구소의 존 벤틀리는 『프로그래밍 진주』에 쓴 글에서, 전문 프로그래머들에게 두 시간을 주고 이진 탐색을 짜게 했더니 열에 한 명 정도만 올바른 프로그램을 냈다고 전했습니다.

2006년에는 구글의 조슈아 블로크가 벤틀리의 책에 실린 프로그램과 프로그래밍 언어 자바의 표준 라이브러리에 같은 버그가 있다고 알렸습니다. 가운데를 $(\mathrm{low} + \mathrm{high})/2$로 계산하는데, 컴퓨터는 정수를 정해진 개수의 비트(0 또는 1을 적는 한 자리)에 담습니다. 자바의 보통 정수는 32비트여서 2,147,483,647보다 큰 수를 담지 못하고, 그보다 커지면 음수로 넘어가 버립니다. 원소가 $2^{30}$(약 10.7억) 개를 넘는 배열에서는 두 번호의 합이 바로 이 범위를 넘칠 수 있습니다. 이 버그는 여러 해 동안 아무도 모르게 숨어 있었습니다.

시험으로는 넣어 본 입력만 확인할 수 있으니, 모든 크기의 배열에서 맞다는 것을 보이려면 '찾는 값이 있다면 늘 low와 high 사이에 있다'는 조건이 반복마다 지켜지고 남은 후보의 수가 매번 줄어든다는 것을 증명해야 합니다. 아래 인용문의 주인인 호어가 1969년 이런 증명을 규칙으로 적은 것이 호어 논리⁠(Hoare logic)⁠입니다. 다만 넘침 버그는 수학의 정수 대신 기계의 정수를 쓴다는 사실까지 규칙에 넣어야 잡힙니다.

소프트웨어를 설계하는 방법은 두 가지입니다. 하나는 너무 단순해서 결함이 없는 것이 분명하게 만드는 것이고, 다른 하나는 너무 복잡해서 분명한 결함이 없게 만드는 것입니다.— 토니 호어, 튜링상 수상 강연 「황제의 낡은 옷」(1980)

스무 고개에는 더 깊은 뜻이 있습니다. 예·아니오 답 하나가 줄 수 있는 정보는 많아야 1비트입니다. 비트는 두 갈래 가운데 하나를 가리키는 정보의 단위이고, $k$비트로는 $2^k$가지를 구별할 수 있습니다. 똑같이 그럴듯한 후보 $N$개 가운데 하나를 가려내려면 $\log_2 N$비트가 필요하니, 어떤 질문 전략도 최악에 $\log_2 N$번보다 적게 물을 수는 없습니다. 이것이 1948년 클로드 섀넌이 정보를 잰 방식, 곧 정보 엔트로피⁠(information entropy)⁠의 출발점입니다. 후보마다 확률이 다르면 흔한 후보를 먼저 묻는 편이 평균적으로 유리하고, 어떤 예·아니오 질문이든 허용할 때 평균 질문 수가 가장 적은 질문 트리가 허프만 부호⁠(Huffman coding)⁠입니다(「짧게 보내기」). 이제 이 생각을 정렬에 그대로 돌려 봅시다. 정렬도 스무 고개입니다. 숨은 것은 수 하나가 아니라 카드들의 순서입니다.

6 · 넘을 수 없는 벽결정 트리⁠(decision tree)⁠와 log₂ n!

이 절의 물음은 이것입니다. 아직 아무도 발명하지 않은 방법까지 포함해, 비교만 쓰는 어떤 정렬 방법도 피할 수 없는 비교 횟수가 있을까? 스무 고개의 생각을 그대로 씁니다. 먼저, 카드 $n$장이 놓일 수 있는 순서는 몇 가지일까요? 첫 자리에 $n$가지, 둘째 자리에 $n-1$가지, …이므로 $n! = n \times (n-1) \times \cdots \times 1$가지입니다(순열⁠, permutation⁠). 늘어놓는 방법의 수를 세는 요령은 「세지 않고 세기」 2절에 있습니다. 카드 세 장 A, B, C라면 A < B < C, A < C < B, B < A < C, B < C < A, C < A < B, C < B < A의 여섯 가지입니다. 비교 정렬⁠(comparison sort)⁠은 이 여섯 가지 가운데 실제 순서가 무엇인지 알아내는 스무 고개입니다. 알아내기만 하면 그 순서대로 카드를 옮기면 되니까요.

어떤 비교 정렬이든 그 행동은 질문의 트리로 그릴 수 있습니다. 첫 질문은 늘 같고, 답에 따라 다음 질문이 정해지며, 질문이 끝나는 곳, 곧 잎⁠(leaf)⁠에는 결론이 적혀 있습니다. 이것을 결정 트리라고 합니다. 아래는 카드 세 장을 정렬하는 삽입 정렬의 결정 트리입니다. 숨은 순서를 로 골라 보세요(잎을 눌러도 됩니다). 노란 길이 그 순서에서 알고리즘이 묻는 질문들입니다. 질문은 번입니다.

이제 증명입니다. 첫째, 잎은 적어도 $n!$개여야 합니다. 서로 다른 두 순서가 같은 잎에 닿으면 알고리즘은 두 경우에 똑같이 카드를 옮길 테니 한쪽은 틀립니다. 순서가 비둘기, 잎이 비둘기집이라면 비둘기집이 모자라서는 안 됩니다(비둘기집 원리⁠, pigeonhole principle⁠). 둘째, 질문을 $d$번까지만 하는 트리는 가지가 매번 둘로 갈라지므로 잎이 많아야 $2^d$개입니다. 질문 한 번이면 잎이 2개, 두 번이면 4개, 세 번이면 8개입니다. 두 사실을 합치면(⟹는 '그러므로'라고 읽습니다)

입니다. 세 장이면 $\log_2 6 \approx 2.58$이니 최악에 3번은 물어야 합니다. 위의 트리가 바로 그렇습니다. 운이 좋으면 2번에 끝나지만(A < B < C나 B < A < C를 골라 보세요), 모든 순서를 2번에 끝낼 수는 없습니다. 잎이 넷뿐이기 때문입니다. 이것이 비교 정렬의 하한⁠(comparison sorting lower bound)⁠입니다.

이 하한은 얼마나 클까요? 곱의 로그는 로그의 합이므로($2^a \times 2^b = 2^{a+b}$이니 $\log_2(xy) = \log_2 x + \log_2 y$), $n! = 1 \times 2 \times \cdots \times n$에서 $\log_2 n! = \log_2 1 + \log_2 2 + \cdots + \log_2 n$이고, 이 합은 곡선 $y = \log_2 x$ 아래의 넓이⁠(area)⁠와 거의 같습니다(「거리를 되찾기」의 적분⁠(integral)⁠). 더 정확한 값은 18세기 런던의 드무아브르와 스코틀랜드의 수학자 제임스 스털링이 구한 스털링 공식⁠(Stirling's formula)⁠ $n! \approx \sqrt{2\pi n}\,(n/e)^n$에서 나옵니다. 드무아브르가 이런 어림으로 이항계수에서 종 모양 곡선을 얻은 이야기는 「도박판에서 온 편지」 6절에 있습니다. 로그를 취하면

입니다. 가운데 항의 1.443은 $\log_2 e$, 곧 $(n/e)^n$의 로그에서 나오는 수입니다. 앞의 항이 모든 것을 좌우합니다. 어떤 비교 정렬도 $n\log_2 n$의 벽을 넘지 못합니다. 카드 천 장이면 적어도 8,530번, 트럼프 한 벌 52장이면 $52! \approx 8 \times 10^{67}$가지 순서 가운데 하나를 가려내야 하니 적어도 226번입니다. 병합 정렬은 천 장을 많아야 8,977번에 끝내니, 이 벽보다 겨우 5%쯤 많을 뿐입니다. 최악의 비교 횟수로 따지면, 폰 노이만의 1945년 방법에는 더 나아질 여지가 5%쯤밖에 없었던 것입니다.

그림에서 카드 수를 골라 보세요($n =$ ). 순서는 가지, $\log_2 n! =$ 이니 하한은 번입니다. 실제로 필요한 최소 횟수는 번, 병합 정렬의 최악은 번, 삽입 정렬의 최악은 번입니다.

작은 $n$에서 하한에 딱 맞추는 일은 끈질긴 퍼즐이었습니다. 흔히 '하한은 늘 딱 맞출 수 있다'고 생각하기 쉽지만, 하한은 '이보다 적게는 안 된다'는 뜻일 뿐 '이만큼이면 된다'는 보장이 아닙니다. 이 퍼즐을 분명한 물음으로 적은 사람은 폴란드의 수학자 후고 슈타인하우스로, 1950년판 『수학의 스냅 사진』에서 물건 $n$개를 두 개씩 비교해 순위를 매기려면 최소 몇 번이면 늘 충분한지를 물었습니다. 그는 전쟁 전 르부프에서 바나흐와 함께 스코틀랜드 카페의 문제들을 적던 사람입니다(「이기는 쪽이 존재한다」 7절). 1959년 수학자 레스터 포드와 셀머 존슨이 내놓은 '병합 삽입⁠(merge insertion)⁠'은 11장까지 하한과 정확히 같은 횟수로 정렬합니다. 그런데 1965년 미국의 컴퓨터 과학자 마크 웰스는 컴퓨터로 모든 경우를 뒤져 12장에는 하한 29번으로는 부족하고 30번이 꼭 필요함을 보였습니다. 13장(34번)은 1994년, 14장과 15장은 2000년대에 확정되었고, 16장에는 하한 45번이 아니라 46번이 필요하다는 것이 2020년대에 들어서야 컴퓨터 탐색으로 밝혀졌습니다. 카드가 더 많아지면 2020년대 기준으로도 정확한 최솟값을 모르는 경우가 대부분입니다.

이 증명에서 눈여겨볼 것은 그 대상입니다. 우리는 병합 정렬이나 퀵정렬을 분석한 것이 아니라, 비교만 쓰는 모든 가능한 알고리즘을 두고 말했습니다. 아직 아무도 생각하지 못한 방법까지 포함해서입니다. 알고리즘을 하나하나 들여다보는 대신 그것이 얻을 수 있는 정보의 양을 세었기 때문에 가능했습니다.

같은 증명을 게임으로 읽을 수도 있습니다. 알고리즘이 비교를 물을 때마다 4절의 매킬로이 같은 적수가, 아직 가능한 순서가 더 많이 남는 쪽으로 답한다고 합시다. 한 번의 답은 후보를 많아야 절반으로 줄일 뿐이니, 적수는 어떤 알고리즘에게서든 적어도 $\log_2 n!$번의 질문을 끌어냅니다. '모든 알고리즘에 대해 어떤 입력이 있어서'라는 하한의 문장이, 알고리즘과 적수가 번갈아 두는 게임에서 적수에게 이기는 전략⁠(winning strategy)⁠이 있다는 말이 되는 것입니다(「이기는 쪽이 존재한다」). 무언가가 불가능하다는 것을 보이는 다른 방법들은 「불가능의 증명」에 모여 있습니다.

이런 하한 증명은 드뭅니다. 어떤 문제를 푸는 빠른 방법이 없다는 것을 보이기는 대개 몹시 어렵고, 그 가장 유명한 예가 아직 풀리지 않은 P 대 NP 문제⁠(P versus NP problem)⁠입니다(「기계가 풀 수 없는 문제」 7절). 정렬은 위와 아래가 거의 딱 맞게 알려진 몇 안 되는 문제입니다. 정리하면, 비교 정렬은 $n!$가지 순서 가운데 하나를 예·아니오로 가려내는 스무 고개이고, 그래서 최악에 적어도 $\log_2 n!$, 대략 $n\log_2 n$번을 물어야 합니다.

7 · 비교하지 않으면카드 분류기와 기수 정렬⁠(radix sort)⁠

이 절의 물음은 이것입니다. 6절의 벽은 정말 모든 정렬 방법을 막을까? 그런데 1절의 카드 분류기는 이 벽에 갇혀 있지 않습니다. 벽의 증명에는 가정이 하나 숨어 있었습니다. 알고리즘이 카드에서 알아낼 수 있는 것은 두 카드의 비교 결과뿐이라는 것입니다. 분류기는 카드 두 장을 비교하는 대신 한 장의 한 열을 읽고 곧바로 열 개의 칸 가운데 하나로 보냅니다. 한 번에 예·아니오의 1비트가 아니라 열 갈래의 답, 곧 많아야 $\log_2 10 \approx 3.3$비트를 얻습니다. 그리고 그 답은 다른 카드와 상관없이 정해집니다.

세 자리 번호가 적힌 카드를 분류기로 정렬해 봅시다. 뜻밖에도 천공 카드 작업자들은 가장 낮은 자리부터 분류했습니다. 일의 자리로 칸에 나누고, 0번 칸부터 차례로 모아 다시 덱을 만든 다음, 십의 자리로 다시 나누고, 마지막으로 백의 자리로 나눕니다. 두 자리 카드 31, 12, 22로 해 봅시다. 일의 자리로 나누면 1번 칸에 31, 2번 칸에 12, 22가 떨어지고, 모으면 31, 12, 22입니다. 이제 십의 자리로 나누면 1번 칸에 12, 2번 칸에 22, 3번 칸에 31이 떨어져 12, 22, 31로 정렬됩니다. 아래 그림에서 분류해 보세요.

▶ 한 판 끝까지 새 카드

낮은 자리부터 해야 하는 까닭은 모으는 방식에 있습니다. 한 칸 안의 카드들은 덱에 있던 순서를 그대로 지킵니다. 십의 자리로 나눌 때 십의 자리가 같은 카드들은 앞 판에서 만든 일의 자리 순서를 유지하고, 그래서 판이 끝나면 끝 두 자리로 정렬됩니다. 같은 값의 순서를 흐트러뜨리지 않는 이 성질을 '안정성⁠(stability)⁠'이라고 합니다. 마지막 판의 기준이 가장 중요한 자리, 곧 백의 자리여야 합니다. 거꾸로 31, 12, 22를 십의 자리부터 나누면 12, 22, 31이 되지만, 이어서 일의 자리로 나누면 31, 12, 22로 되돌아가 버립니다. 마지막 판이 앞 판의 결과를 덮어쓰기 때문입니다. 이것이 기수 정렬입니다. 10진법⁠(positional notation)⁠으로 적은 번호의 자릿수 하나하나가 분류의 한 판이 됩니다. 이 방법은 작업자들 사이에 먼저 퍼진 요령이었던 것으로 보이며, 크누스는 1929년 뉴질랜드 출신의 천문학자 레슬리 코미가 천공 카드 기계를 소개한 글을 첫 출판 기록으로 꼽습니다.

비용은 간단합니다. 카드 $n$장, 자릿수 $d$개이면 카드를 옮기는 일이 $n \times d$번, 비교는 0번입니다. 인구조사의 카드처럼 자릿수가 정해져 있으면 카드 수에 정비례하니 $n\log_2 n$보다 느리게 자랍니다. 1954년 MIT의 해럴드 시워드는 초기 컴퓨터 월윈드를 만든 MIT의 월윈드 계획에서 석사 논문을 쓰며 이 방법을 컴퓨터로 옮겼습니다. 같은 논문에는 값마다 몇 개인지 먼저 세어 각 값이 들어갈 자리를 미리 계산하는 계수 정렬⁠(counting sort)⁠도 적혀 있습니다. 편지의 우편번호도 같은 원리입니다. 미국은 1963년 다섯 자리 ZIP 코드를 도입했고, 한국은 2015년 다섯 자리 국가기초구역 번호로 우편번호를 바꾸었습니다. 앞자리부터 지역, 그 안의 구역을 뜻하는 번호는 기계가 자리 하나씩 읽어 칸을 고르기에 알맞습니다.

그렇다면 벽은 무너진 걸까요? 꼭 그렇지는 않습니다. 기수 정렬은 '두 카드의 비교'라는 약속을 깨고 카드에 적힌 자릿수라는 구조를 들여다봅니다. 그리고 카드 $n$장의 번호가 모두 다르려면 자릿수가 적어도 $\log_{10} n$개(10을 몇 번 곱해야 $n$이 되는가, 천 장이면 3)는 있어야 하므로, 번호가 모두 다를 때 $n \times d$는 적어도 $n\log_{10} n$, 결국 $n\log n$ 꼴로 돌아옵니다. 기수 정렬이 이기는 것은 번호의 범위가 좁거나 같은 값이 많은 경우, 곧 인구조사처럼 나이, 성별, 지역 번호로 수천만 장을 가를 때입니다. 하한의 증명은 틀리지 않았습니다. 다만 모든 증명이 그렇듯 가정 위에서만 성립했습니다. 무엇을 할 수 있는 기계인가를 바꾸면 한계도 바뀝니다.

알파벳이 없는 문자에서는 '사전 순서'부터 정해야 했습니다. 1716년 청나라 강희제의 명으로 나온 『강희자전』은 한자 4만 7천여 자를 214개의 부수로 묶고, 같은 부수 안에서는 부수를 뺀 나머지 부분의 획수 차례로 늘어놓았습니다. 부수들 자체도 획수 차례로 놓였습니다. 이 214부수 체계는 1615년 명나라 매응조의 『자휘』에서 먼저 쓰였습니다. 부수라는 첫째 열쇠로 칸을 나누고 획수라는 둘째 열쇠로 칸 안을 줄 세우니, 열쇠가 둘인 줄 세우기입니다. 이것을 기수 정렬로 하려면 이 절에서 본 대로 덜 중요한 열쇠인 획수로 먼저 나누고 부수로 마지막에 나누면 됩니다. 한글의 차례도 사람이 정한 약속입니다. 1446년의 『훈민정음』은 자음을 소리 나는 자리에 따라 ㄱ, ㅋ, ㆁ, ㄷ, ㅌ, ㄴ, …의 차례로 늘어놓았습니다. 1527년 역관 최세진의 한자 학습서 『훈몽자회』는 받침으로도 쓰이는 여덟 글자 ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ, ㆁ을 앞세워 차례를 바꾸었고, '기역, 니은' 같은 자모 이름을 처음으로 적어 남겼습니다. 오늘날 국어사전의 ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ, ㅈ, ㅊ, ㅋ, ㅌ, ㅍ, ㅎ 차례는 1933년 조선어학회의 「한글 맞춤법 통일안」에서 굳어졌습니다.

8 · 줄 세우는 세계데이터베이스, 팀소트⁠(Timsort)⁠, 그리고 인구조사의 그늘

이 절의 물음은 이것입니다. 벽의 위치를 안 뒤에, 실제 세계는 어떻게 줄을 세울까? 그리고 무엇을 기준으로 줄 세울지는 누가 정할까?

1962년 캘리포니아 공과대학의 대학원생이던 크누스는 컴파일러⁠(compiler)⁠, 곧 사람이 쓴 프로그램을 기계가 실행하는 명령으로 옮겨 주는 프로그램에 관한 책을 써 달라는 청탁을 받았습니다. 이 책은 『컴퓨터 프로그래밍의 기술』이라는 연작으로 불어났고, 1968년 스탠퍼드로 옮긴 그는 1973년 3권 『정렬과 탐색』을 펴냈습니다. 이 글에 나온 역사의 상당 부분, 곧 폰 노이만의 원고, 코미의 기수 정렬, 모클리의 이진 탐색, 최소 비교 횟수의 퍼즐은 이 책이 추적해 기록한 것입니다. 크누스는 1974년 튜링상을 받았고, 2020년대에도 이 연작의 다음 권들을 쓰고 있습니다.

실제 세계의 자료는 무작위로 섞인 카드가 아닙니다. 이미 대부분 정렬된 목록에 몇 개가 새로 붙거나, 오름차순과 내림차순 구간이 이어져 있기 일쑤입니다. 2002년 프로그래머 팀 피터스가 프로그래밍 언어 파이썬을 위해 만든 팀소트는 이 점을 노립니다. 목록에서 이미 정렬된 구간을 찾아내고, 짧은 구간은 삽입 정렬로 늘린 뒤, 구간들을 병합 정렬처럼 합칩니다. 2절에서 본 '거의 정렬된 자료에 강한' 삽입 정렬과 3절의 병합이 한 몸이 된 셈입니다. 자바(2011년)와 안드로이드도 이 방법을 받아들였습니다. 2015년에는 암스테르담의 네덜란드 국립 수학·정보과학 연구소(CWI) 등의 연구진이 증명의 모든 단계를 기계가 확인하는 증명 도구(「증명은 프로그램이다」 9절)로 이 알고리즘이 옳다는 것을 검증하려다가, 드문 입력에서 자바 구현이 실패하는 버그를 찾아냈습니다. 5절의 교훈이 되풀이된 것입니다.

정렬은 데이터베이스의 뼈대이기도 합니다. 1970년 시애틀의 보잉 과학 연구소에서 컴퓨터 과학자 루돌프 바이어와 에드워드 매크레이트는 정렬된 열쇠들을 가지가 수백 개인 넓고 얕은 트리에 담는 B-트리⁠(B-tree)⁠를 내놓았습니다. 수억 개의 기록에서도 디스크를 몇 번만 읽으면 원하는 것을 찾고, 범위 안의 기록을 차례대로 훑을 수 있습니다. 같은 해 IBM 새너제이 연구소의 영국 출신 컴퓨터 과학자 에드거 코드는 자료를 표와 관계로 다루는 관계형 모형을 발표했습니다. 두 표를 이을 때 양쪽을 정렬한 뒤 병합하는 방법은 오늘날에도 기본 연산입니다.

순서가 필요 없고 찾기만 하면 될 때는 열쇠를 칸 번호로 바로 바꾸는 해시 테이블⁠(hash table)⁠이 쓰입니다. 이것은 7절의 분류기가 카드를 칸에 떨어뜨리는 생각을 극단까지 밀고 간 것입니다. 검색 엔진은 낱말마다 그것이 나오는 문서들을 정렬해 둔 색인을 만들고, 찾은 문서들을 페이지랭크⁠(PageRank)⁠ 같은 점수로 다시 줄 세워 보여 줍니다. 무엇이 첫 화면에 오는지가 곧 정렬의 결과입니다.

줄 세우기의 역사에는 그늘도 있습니다. 홀러리스의 기계는 나라가 국민을 세고 가르는 일을 값싸게 만들었지만, 무엇으로 가를지는 기계가 아니라 사람이 정했습니다. 1933년 6월, 나치가 집권하고 몇 달 뒤 독일은 인구조사를 치렀습니다. 조사표에는 종교를 묻는 항목이 있었고, 집계는 IBM의 독일 자회사 데호마크의 천공 카드 기계로 이루어졌습니다. 뒤이은 여러 등록과 조사에서도 천공 카드는 유대인을 가려내 세는 데 쓰였습니다. 2001년 기자 에드윈 블랙은 『IBM과 홀로코스트』에서 IBM 본사가 이를 알고도 사업을 이어 갔다고 주장했고, IBM은 전쟁 중 데호마크가 나치 당국의 통제 아래 있었다고 반박했습니다. 본사가 어디까지 알고 관여했는지는 역사가들 사이에서도 평가가 갈립니다.

민주 국가도 예외가 아니었습니다. 2차 세계대전 중 미국에서 일본계 주민 12만여 명이 강제 수용될 때 인구조사국은 지역별 집계를 제공했습니다. 2007년 통계학자 마고 앤더슨과 윌리엄 셀처는 인구조사국이 1943년 워싱턴 일대 일본계 미국인의 이름과 주소까지 재무부에 넘겼음을 보여 주는 문서를 찾아냈습니다. 비밀 보장을 약속하고 모은 정보였지만, 1942년의 전시 법이 그 보호를 잠시 거두어 둔 때였습니다. 이런 역사는 오늘의 규칙을 낳았습니다. 1983년 12월 카를스루에의 독일 연방헌법재판소는 그해 치를 예정이던 인구조사의 법률 일부를 위헌으로 보고, 자기에 관한 정보가 어떻게 쓰일지를 스스로 정할 권리를 기본권으로 인정했습니다. 조사는 1987년으로 미뤄졌고, 이 판결은 유럽 개인정보 보호법의 중요한 뿌리가 되었습니다. 인도의 식민 당국이 인구조사 자료로 카스트를 서열화하려 한 이야기(「까마귀와 택시」 6절)와 함께 보면, 정렬의 수학은 중립이지만 무엇을 기준으로 줄 세우는가는 언제나 사회의 선택이었습니다.

캐나다의 철학자 이언 해킹은 이 물음을 한 걸음 더 밀고 갔습니다. 카드의 번호는 어떻게 줄 세우든 그대로입니다. 그런데 사람을 나누는 분류는 분류된 사람에게 되돌아옵니다. 사람들은 자기가 어느 칸에 들었는지 알고, 그 칸에 맞춰 살거나 맞서며, 그렇게 달라진 사람들 때문에 분류도 다시 고쳐집니다. 해킹은 1986년의 글 「사람 만들어 내기」와 그 뒤의 글들에서 이것을 '되먹임⁠(feedback)⁠ 효과'라 부르고, 사람의 무리를 세고 나누는 통계⁠(statistics)⁠가 이 되먹임을 돌리는 큰 엔진이라고 보았습니다. 반대쪽에는 좋은 분류란 세계에 이미 있는 구분을 찾아낼 뿐이라는 실재론의 생각이 있고, 해킹도 모든 분류가 지어낸 것이라고 하지는 않았습니다. 그가 짚은 것은, 분류를 알아차리지 못하는 대상과 달리 사람은 줄을 세우는 일 자체로 바뀔 수 있다는 점입니다.

1870년부터 오늘까지. 위의 연표에서 인구조사와 천공 카드(분홍 줄)가 20세기 전반을 채우고, 1945년부터 1976년 사이 수학 줄(파랑)에 병합 정렬, 퀵정렬, 힙, 하한, 표기법이 몰려 있는 것을 보세요. 지도의 선은 사람과 생각이 오간 길입니다. 모스크바의 기계 번역에서 나온 퀵정렬이 런던으로 건너간 길도 있습니다.

9 · 이어지는 길순서가 여는 문

'줄 세우기'와 '비교 횟수의 하한'은 수학과 컴퓨터 과학의 여러 곳으로 이어집니다.

• 세기: 하한의 핵심은 순서의 가짓수 $n!$을 세는 일이었습니다. 순열, 조합, 그리고 직접 세지 않고 세는 방법들은 「세지 않고 세기」로 이어집니다.
• 정보: $\log_2 n!$은 카드의 순서를 적는 데 필요한 비트 수이기도 합니다. 어떤 무손실 압축⁠(lossless compression)⁠도 엔트로피⁠(entropy)⁠ 밑으로 내려갈 수 없다는 원천 부호화 정리⁠(source coding theorem)⁠는 이 하한과 같은 모양의 논증입니다(「짧게 보내기」).
• 배우는 나무: 기계 학습⁠(machine learning)⁠의 결정 트리도 예/아니오 질문을 이어 가는 같은 모양의 나무입니다. 다만 가능한 순서를 모두 가려내는 대신 자료를 나누어 새 자료의 답을 맞히는 것이 목표이고, 질문마다 엔트로피를 가장 많이 줄이는 것을 욕심껏 고릅니다(「배우는 기계」).
• 그래프: 모든 도시를 가장 짧은 전선으로 잇는 최소 신장 트리⁠(minimum spanning tree)⁠는 변을 길이 순으로 정렬한 뒤 순환을 만들지 않는 것부터 고르는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠으로 풀립니다. 우선순위 큐로 달리는 최단 경로 찾기, 곧 데이크스트라가 만든 다익스트라 알고리즘은 「일곱 다리의 도시」에 있습니다.
• 짝짓기: 의대 졸업생과 병원이 서로의 선호를 순위로 적어 내면, 그 줄 세운 목록들에서 안정 매칭⁠(stable matching)⁠이 나옵니다(「짝을 찾는 알고리즘」).
• 무질서 속의 질서: 서로 다른 수 $n^2+1$개를 어떻게 늘어놓아도 길이 $n+1$인 증가하는 부분 수열이나 감소하는 부분 수열이 반드시 숨어 있습니다. 1935년 에르되시와 세케레시의 정리로, 완전히 뒤섞인 줄은 없다는 램지 이론⁠(Ramsey theory)⁠의 한 얼굴입니다(「완전한 무질서는 없다」).
• 가까운 이웃: 새 자료와 가장 닮은 예를 찾는 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠는 거리를 재고 줄 세우는 일입니다. 거리를 무엇으로 재느냐에 따라 줄이 바뀝니다(「까마귀와 택시」).
• 게임: 결정 트리의 하한은 알고리즘과, 답을 가장 심술궂게 골라 주는 적수 사이의 게임입니다. '모든'과 '어떤'이 번갈아 나오는 문장을 두 사람의 게임으로 읽는 관점, 그리고 체스 끝내기를 끝에서부터 거꾸로 따져 푼 이야기는 「이기는 쪽이 존재한다」에 있습니다.
• 증명: 팀소트의 버그는 시험이 아니라 증명을 시도하다 드러났고, 이진 탐색의 넘침 버그도 기계의 정수를 규칙에 넣은 증명이라면 잡을 수 있었습니다. 프로그램이 옳다는 것을 기계가 확인하는 증명으로 보이는 일은 「증명은 프로그램이다」로 이어집니다.
• 계산의 한계: 결정 트리 논증은 '빠른 방법은 없다'를 증명한 드문 성공입니다. 같은 종류의 질문이 훨씬 어려운 곳에 P 대 NP와 정지 문제⁠(halting problem)⁠가 있습니다(「기계가 풀 수 없는 문제」).