퀵정렬(Quick Sort) - 찰스 앤터니 리처드 호어(1934~)에 의해서 고안된 정렬로 매우 빠른 정렬입니다.
퀵정렬의 이해는 재귀와 분할정복(divide and conquer)에 대한 이해를 기초로 합니다.
분할정복은 재귀를 푸는 방식인데, 큰 덩어리의 문제를 작은 덩어리로 나누어 해결하는 방식입니다.
작은 덩어리로 나눌 때는 큰 덩어리와 작은 덩어리가 구조적으로 같아야 합니다.
2014/02/26 - [알고리즘] - 하노이탑 재귀호출 알고리즘
본론에 앞서 워밍업을 해봅시다.
①번을 보면 배열의 양끝을 L과 R로 표시해둡니다. 여기서 L위치의 값을 중심값으로 정합니다. 영상처럼 중심값(pivot)을 중심으로 작은 값은 왼 편으로, 큰 값은 오른 편으로 이동하는 것이 목적입니다. 여기서 이동 된 값들의 순서는 알파벳 순서라고 보장할 수 없기 때문에, 퀵정렬은 불안정 정렬에 속합니다.
②번 과정은 R위치의 값과 중심값 A를 비교합니다. R위치의 값이 중심값 보다 작은 값이 나올 때까지 위치를 왼쪽으로 옮겨가며 비교합니다.중심값 보다 작은 값을 찾는 이유는 L의 위치로 보내기 위해서 입니다. 결국 L과 R이 만나게 되는데 이 위치가 ⑤번과정에서 보듯이 중심값이 됩니다. 이 위치를 중심으로 L이 거쳐온 곳은 중심값 보다 작은 값들로 채워지게 되고 R이 거쳐온 곳들은 중심값 보다 큰 값들로 채워지게 됩니다. 여기선 중심값이 A기 때문에 더 작은 값들이 없어서 R의 위치만 최초 L의 위치까지 이동했네요.
아무튼 위 논리로 L과 R이 만나는 곳을 중심으로 대소 관계가 확실히 정해지기 때문에 L과 R이 만나는 곳은 ⑥정렬이 된 값으로 확신할 수 있습니다.
정렬된 값을 중심으로 왼 편 값들과 오른 편 값들을 다시 새로운 정렬 대상으로 위 작업을 반복하면 됩니다. 이것이 재귀의 분할정복입니다.
① A는 정렬된 값이고, 왼 편(없음)과 오른 편 값들로 같은 작업 반복하게 됩니다.
② 오른편 값들의 처음값 위치를 L 끝값 위치를 R로 정합니다. L위치 값을 중심값으로 합니다. ③R값부터 중심값과 비교하여 왼편으로 이동하며 작은 값을 찾아갑니다. ④찾은 값을 L위치로 복사합니다.
⑤,⑥ L위치의 값을 오른쪽으로 이동하며 중심값 보다 큰 값을 찾아갑니다. 찾아서 R위치로 복사합니다.
이후로 L과 R을 번갈아 가면서 위 작업을 L과 R의 위치가 같아질 때 까지 반복합니다.
발상은 기발하지만 원리는 간단합니다.
위 방법은 보편적인 방법입니다. 여기서 보편적이라 함은 인터넷에서 퀵정렬을 찾아보면 위 방법은 쉽게 찾을 수 있기 때문입니다.
아이디어는 같지만 약간 다른 방법을 생각해 보겠습니다.
지금까지 살펴본 방법은 L값과 R값을 따로 따로 움직였습니다. 조건에 만족한 값을 각각 상대 위치에 복사하는 방식인데, 여기서 상대 위치는 조건에 맞는 경우 R의 위치의 값은 L값으로 L위치의 값은 R값으로 보냈다는 뜻입니다. 여기서 이 상대 위치의 진정한 의미는 중심값보다 왼편, 중심값보다 오른편을 의미합니다.
여기까지 이해가 되셨다면, L값과 R값을 동시에 움직이면서 양쪽 값이 동시에 조건에 맞는 경우 두 값을 교환해 나가는 것은 어떨까요. 위에서 말한 진정한 의미에 부합합니다.
간단한 알고리즘이지만 완벽하게 알고리즘을 짜려면 그리 만만하지 않다고 생각됩니다.