본문 바로가기

알고리즘/알고리즘 도감

퀵 정렬

지난 글: [알고리즘] - 병합 정렬

 

퀵 정렬(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)'라고 한다. 

 

참고 서적 :

'알고리즘 > 알고리즘 도감' 카테고리의 다른 글

이진 탐색  (0) 2022.06.14
선형 탐색  (0) 2022.06.13
병합 정렬  (0) 2022.06.11
힙 정렬  (0) 2022.06.10
삽입 정렬  (0) 2022.06.09