토니 호어

튜링상 관련 업적

퀵 정렬

컴퓨터를 사용하다 보면 알게 모르게 정렬^sort 기능을 사용할 때가 많다. 일정을 정리할 때나 이메일을 정리할 때 날짜 순서대로 목록을 만들며, 주소록에서는 알파벳 순서로 목록을 만든다. 학교에서는 학생들의 등수를 매기기 위해서 시험 성적 순서대로 목록을 만들고, 회사에서는 업무를 위해 정보를 특정 순서대로 배열하는 일이 다반사이다.

정렬 작업은, 다루어야 하는 데이터의 양이 늘어나면 급격하게 힘들어진다. 10개의 데이터를 정렬할 때와 100개의 데이터를 정렬할 때를 비교하면 시간이 10배로 늘어나는 것이 아니라 훨씬 더 많이 늘어난다. 그래서 더 효율적인 정렬 방법이 필요해진다.

컴퓨터에서 정렬 작업의 효율은 단순히 시간만 따질 수 없다. 컴퓨터의 자원은 제한되어 있고, 특히 메모리 용량이 치명적이다. 그래서 시간도 적게 걸리고 메모리도 덜 사용하는 알고리듬이 사랑받을 수밖에 없다. 퀵 정렬^Quicksort이 사랑받는 이유가 거기에 있다.

아래와 같이 주어진 6개의 숫자를 정렬하는 방법에 대해 생각해보자.

4 6 5 3 9 8

우리가 가장 상식적으로 생각해낼 수 있는 방법은, 일단 가장 작은 수를 찾는 것이다. 위의 숫자가 각각 종이 카드에 적혀 있다고 가정해보자. 먼저 4가 쓰여 있는 카드를 손에 쥔다. 그리고 그다음 숫자와 차례로 비교한다. 만약 더 작은 숫자가 나타나면 들고 있던 카드를 내려놓고 그 더 작은 숫자가 적혀 있는 카드를 손에 쥔다. 이런 식으로 진행하면 가장 마지막에는 3번 카드가 손에 남게 된다. 이제 가장 작은 숫자를 구했으니 그것은 옆에 내려놓고 다시 남아 있는 5장의 카드 중에서 가장 작은 수를 구한다. 이번에는 4번 카드가 마지막에 손에 남을 것이다. 이런 과정을 반복하면 오름차순으로 정렬하게 된다. 이런 방식을 버블 정렬^{bubble sort}이라고 부른다. 토니가 모스크바에서 정렬 방식을 고민했을 때 맨 처음에 머리에 떠올렸던 방식이라고 한다.

버블소트는 쉽게 이해되는 장점이 있지만 시간이 너무 오래 걸리는 단점이 있다. 정렬해야 할 데이터의 개수가 n개라고 한다면 ‘가장 작은 데이터를 찾기 위해 전체를 훑는 작업‘을 n-1번이나 해야 한다. 데이터의 개수가 많아질수록 엄청나게 오랜 시간이 걸린다. 이 점을 토니도 깨달았고 그래서 더 좋은 방법이 있을지 고민했던 것이다.

퀵 정렬은 ‘쪼개서 정복하기^{divide-and-conquer}‘ 방식이라고 이해하면 좋겠다. 전체 데이터를 두 개의 그룹으로 쪼갠 후에 각 그룹을 따로 정렬하는 식이다. 그런데 두 개의 그룹에서 정렬을 수행한 결과가 겹친다면 일이 오히려 더 복잡해질 수 있다. 위의 예를 보자. 정확히 절반으로 데이터를 나누면 4 6 5와 3 9 8로 나뉘게 된다. 각각을 정렬하면 4 5 6과 3 8 9가 된다. 그런데 안타깝게도 이 결과를 그대로 붙여서 쓸 수가 없다. 즉 4 5 6 3 8 9로 하자니 3이 6보다 작고, 3 8 9 4 5 6으로 하자니 4가 9보다 작다. 굳이 둘로 나누어 정렬할 이유가 없어지는 셈이다. 이런 상황을 피하려면 두 개의 그룹으로 나누었을 때 한쪽 그룹의 가장 큰 값이 다른 쪽 그룹의 가장 작은 값보다 작아야 한다. 만약 위의 예에서 6개의 숫자를 4 6 5 3과 9 8로 쪼갠 후에 각각 정렬하게 되면 3 4 5 6과 8 9가 된다. 이제 이 결과를 그대로 이어 붙인 3 4 5 6 8 9는 완벽한 정답이다.

따라서 퀵 정렬에서 가장 중요한 것은 주어진 데이터를 어디에서 쪼갤 것인가이다. 이를 피벗팅^pivoting이라고 부르는데 한쪽 그룹의 가장 큰 값이 다른 쪽 그룹의 가장 작은 값보다 작도록 그룹을 만드는 과정이다.

퀵 정렬의 또 다른 특징은 재귀적 호출이다. 피벗팅을 통해서 데이터를 두 개의 그룹으로 나눈 후에는 이제 각 그룹에 대해 정렬해야 한다. 그런데 이 정렬도 역시 퀵 정렬을 사용한다. 따라서 퀵 정렬 알고리듬 안에서 퀵 정렬 알고리듬을 사용하게 된다.

퀵 정렬이 항상 버블 정렬보다 효율적이지는 않다. 최악의 상황에는 동일한 성능을 보인다. 하지만 평균적으로는 퀵 정렬이 버블 정렬보다 더 빠르다. 정렬 알고리듬은 이 외에도 여러 가지가 있지만 퀵 정렬이 가장 대중적으로 사용되고 있다.

1 2 3 4 5 6