지난 글: [알고리즘] - 병합 정렬
퀵 정렬(quick sort)에서는 기준이 되는 수(피봇(pivot)이라 함)를 수열 안에서 임의로 하나를 선택한다. 그리고 피봇 이외의 수를 '피봇보다 작은 수'와 '피봇 이상인 수'의 두 그룹으로 나누고 이것을 아래와 같이 배치한다.
'피봇보다 작은 수' < 피봇 < '피봇 이상인 수'
다음은 각 [ ] 안을 정렬만 하면 전체가 정렬된다. [ ] 안을 정렬할 때도 다시 퀵 정렬이 사용된다.
1
3 5 8 1 2 9 4 7 6
퀵 정렬의 작업 순서는 먼저 기준이 되는 수(피봇)를 수열 안에서 임의로 하나 선택한다. 여기서는 4로 한다.
2
3 5 8 1 2 9 (4) 7 6
피봇 이외의 각 숫자를 피봇과 비교해 간다. 피봇보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽으로 이동한다.
5 8 1 2 9 (4) 7 6
3
먼저 3과 피봇인 4를 비교한다. 3 < 4 이므로 3을 왼쪽으로 이동한다.
3
8 1 2 9 (4) 7 6
3 5
다음은 5와 피봇인 4를 비교한다. 5 > 4 이므로 5를 오른쪽으로 이동한다.
(4)
3 1 2 5 8 9 7 6
다른 숫자도 같은 방식으로 비교해 이동하여 위와 같은 결과를 얻는다.
4
3 1 2 (4) 5 8 9 7 6
피봇인 4를 배치한다. 그럼 4의 왼쪽에는 4보다 작은 숫자가, 오른쪽에는 4보다 큰 숫자가 나열된다. 따라서 왼쪽과 오른쪽을 각각 정렬하면 전체 정렬이 완료된다.
5
5 8 9 7 (6)
각각의 정렬도 같은 방식으로 진행한다. 먼저 오른쪽 그룹을 보자. 피봇이 될 수 하나를 임의로 선택한다. 여기서는 6이 되었다.
6
5 (6) 8 9 7
피봇인 6과 각 숫자를 비교해 작으면 왼쪽, 크면 오른쪽으로 이동했다. 왼쪽은 5만 있으므로 정렬이 끝난 상태다. 오른쪽은 같은 방법으로 피봇을 선택해 정렬한다.
7
(8) 9 7
8이 피봇으로 선택됐다.
7 (8) 9
9와 7을 8과 비교해 좌우에 배분한다. 8의 좌우에는 하나의 숫자밖에 없으므로 작업이 완료된다. 이것으로 7 8 9가 정렬 완료 상태가 된다.
8
5 6 7 8 9
한 단계 위로 돌아가 7 8 9가 정렬됐으므로 5 6 7 8 9가 정렬 완료 상태가 된다. 그 결과, 첫 피봇인 4의 오른쪽이 정렬 완료 상태가 된다.
9
3 1 2 4 5 6 7 8 9
|
1 2 3 4 5 6 7 8 9
왼쪽도 마찬가지 방식으로 정렬하면 전체 정렬이 완료된다.
퀵 정렬은 '분할병합법'의 일종이다. 원래는 두 개의 자식 문제(피봇보다 작은 것과 피봇 이상인 것)로 분할하고 두 개의 자식 문제를 각각 해결한다. 각 자식 문제가 정렬 완료 상태가 되면 각각을 단순히 붙이기만 하면(병합) 원래 수열을 정렬한 결과를 얻을 수 있다. 이 자식 문제를 해결하는 부분에도 퀵 정렬이 사용되며, 이 퀵 정렬 안에서도 다시 퀵 정렬이 사용된다. 자식 문제에 숫자가 하나만 남으면 정렬이 끝난다.
이처럼 알고리즘 내부에 알고리즘 자신을 적용하는 것을 '재귀(recursive)'라고 한다.
참고 서적 :
