선택정렬 vs 퀵 정렬

어떻게 하면 이름을 알파벳순으로 배치할 수 있을까? 그런 예비 단계 없이는 이진 검색을 사용할 수 없다. 여기에서 또 다른 알고리즘인 정렬이 등장한다 정렬은 항목을 순서대로 배열해서 검색이 빨리 실행될 수 있도록 해준다.

 이진 검색으로 효율적으로 찾을 수 있도록 사전에 이름을 알파벳순으로 정렬하고 싶다고 가정해 보자. 먼저 살펴볼 알고리즘은 선택 정렬이다 이렇게 불리는 까닭은 아직 정렬되지 않은 항목 중에서 다음 이름을 계속 선택하기 때문이다. 이는 앞서 보았던 방 안에서 가장 키 큰 사람을 찾는 기법에 바탕을 두고 있다.

 맨 처음 단어와 다음 이름을 비교해서 알파벳이 앞에 오는 것을 첫 번째 이름을 하고, 비교해야 할 대상들을 차례대로 비교해가면서 알파벳순으로 정렬한다 그 다음 2번째로 오는 알파벳을 찾기 위해서 다시 한번 반복하며 끝까지 알파벳 순으로 정렬된 목록을 만들어 낸다. 

 이름을 훑어보는 횟수는 원래 항목의 수에 정비례한다. 하지만 훑어볼 때마다 항목의 수가 한 개씩 줄어들기 때문에 일반적으로 필요한 일의 양은 N개의 단어를 정렬할 때에 다음과 같이 계산된다

N + (N -1) + (N -2) …+ 2 + 1

이 수열의 합계는 N × (N +1) / 2 이 되고, 2로 나누는 것을 무시하면 일의 양은 N² + N에 비례한다. N이 커짐에 따라 N²은 금방 N보다 훨씬 큰 값이 되므로 결과적으로 일의 양은 N², 즉 N의 제곱에 거의 비례하게 되는데, 이러한 증가율을 2차라고 한다. 2차는 선형보다 효율이 훨씬 더 낮다. 만약 정렬할 항목의 수가 2배가 되면 4배의 시간이 걸릴 것이고, 10배라면 100배의 시간이 걸릴 것이다. 항목의 수가 1,000배라면 1,000,000배의 시간이 걸린다. 썩 좋지 않다

 다행스럽게도 훨씬 더 빨리 정렬하는 방법이 있다. 한 가지 기발한 방법을 살펴보자. 바로 퀵 정렬이라는 알고리즘으로 영국인 컴퓨터과학자인 토니 호어가 1959년경에 고안했다. 퀵 정렬은 명쾌한 알고리즘으로, 분할 정복의 훌륭한 사례다.

 선택 정렬보다 단순화된 형태의 퀵 정렬을 사용하여 이름을 정렬하려면, 먼저 이름을 한 번 훑어보면서 첫 글자가 A에서 M까지인 이름을 한 그룹으로 모으고 N에서 Z까지인 이름을 다른 그룹으로 모은다. 이렇게 하면 그룹이 2개 생기고, 각각에 절반 정도의 이름이 들어간다고 가정한다. 이제 A부터 M 그룹을 훑어보면서 A부터 F까지를 하나로, G부터 M까지를 하나로 모은다. 그리고 N-Z 그룹을 훑어보면서 N부터 S까지를 하나로, T부터 Z까지를 하나로 모은다. 이 시점까지 이름 전체를 두 번 훑어보았고, 네 개의 그룹으로 나누었으며 각각의 그룹은 전체 이름의 1/4 정도를 담고 있다.

다음으로는 각 그룹을 훑어보면서 A-F 그룹을 ABC와 DEF로 분리하고, G-M 그룹은 GHIJ와 KLM으로 분리하고, N-S와 T-Z 그룹에 대해서도 같은 식으로 나눠주면 여덟 개의 그룹이 생긴다. 그리고 한두 번 더 훑어보면 이름을 한 개씩 담은 그룹을 갖게 되고, 이름들은 알파벳순이 될 것이다.

 퀵 정렬에는 얼마나 많은 일이 필요했을까? 단계의 수는 N이 1이 될때까지 2로 나누는 횟수다. 이 값은 밑수 2에 대한 N의 로그로, N이 16이라고 가정했을 때 4가 된다. 따라서 일의 양은 16개의 이름에 대해서 16 log₂16이다. 만일 데이터 전체를 4번 훑어본다면 연산이 64번 일어나는 것이고, 이는 선택 정렬에서 연산이 136번 일어나는 것보다 현저히 적다. 이는 이름이 16개일 때 이야기며, 이름이 더 많아지면 퀵 정렬의 장점은 훨씬 더 커진다.

 

이 알고리즘, 항상 데이터를 정렬하지만 그룹을 나눌 때마다 거의 같은 크기의 덩어리로 나눠야만 효율적이다. 실제 데이터를 대상으로 할 때, 퀵 정렬은 매번 거의 같은 크기의 두 그룹으로 나눌 수 있도록 중간 데이터 값을 추측해야만 한다. 실제로는 몇 개 항목에 대해 표본 조사를 함으로써 이 값을 충분히 잘 추정할 수 있다. 일반적으로 퀵 정렬로 N개 항목을 정렬하려면 약 NlogN번의 연산이 필요하다. 즉, 작업의 양은 N×logN에 비례한다. 선형보다는 효율이 낮지만 심하지는 않고, N이 조금이라도 크다면 2차, 즉 N² 보다 훨씬 효율적이다. 

시험 삼아 아홉 자릿수 1천만 개를 무작위로 생성하여 선택 정렬(N², 2차)과 퀵 정렬(NlogN) 방법으로 다양한 크기의 그룹을 정렬하는 데 얼마나 걸리는지 재보았다. 퀵 정렬의 실행 시간이 예상대로 NlogN 비율로 증가하는 것을 볼 수 있고, 선택 정렬은 10,000개 정도까지는 실행 가능한 수준이라는 것도 확인할 수 있다. 모든 단계에서 선택 정렬은 퀵 정렬보다 성능이 압도적으로 뒤처지며, 경쟁이 되지 않는 수준이다.

 선택 정렬이 100,000개의 항목을 처리하는 데 걸리는 시간이 10,000개를 처리하는 시간에 비해 100배 클 것으로 예상했겠지만 실제로는 거의 200배 크다 캐싱의 영향일 수 있다. 수가 캐시에 모두 들어가지 못하면서 정렬이 느려진 것이다. 이 현상은 계산 과정을 이론적으로 추상화한 것과 프로그램이 실제로 계산을 수행하는 상황 간의 차이를 잘 보여준다