[알고리즘과 자료구조] 퀵 정렬에 대해 알아보기

📖 '누구나 자료구조와 알고리즘' 책을 공부한 내용을 담고 있습니다.

13장 속도를 높이는 재귀 알고리즘

실제 배열을 정렬할 때 버블 정렬과 선택 정렬, 삽입 정렬은 잘 사용하지 않는다. 컴퓨터 언어의 내장 함수를 사용해 시간과 노력을 아껴준다. 그 중 퀵 정렬(Quicksort)은 정렬 알고리즘으로 많이 쓰인다.

퀵 정렬 동작 방식을 통해 재귀가 어떻게 알고리즘의 속도를 크게 향상시키는지 배워보자.

13.1 분할

배열을 분할(partition)한다는 것은 배열로부터 임의 수를 가져와(피벗) 피벗보다 작은 모든 수는 피벗의 왼쪽에 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다.

0	5	2	1	6	3

• 일관된 설명을 위해 가장 오른쪽 값을 항상 피벗으로 고른다. -> 3
• 2개의 포인터는 가장 왼쪽과 오른쪽 값을 가르킨다.

0	5	2	1	6	3
↑				↑	피벗

다음과 같은 단계에 따라 실제로 분할한다.
1. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 이어서 오른쪽 포인터를 한셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 또는 배열 맨 앞에 도달해도 멈춘다.
3. 오른쪽 포인터가 멈춘 후에는 둘 중 하나를 선택해야 한다.왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한 값을 교환한 후, 1,2,3단계를 반복한다. 왼쪽 포인터가 오른쪽 포인터에 도달했으면 (또는 넘어섰으면) 4단계로 넘어간다.

4. 끝으로 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환한다.

분할이 끝나면 피벗 왼쪽에 잇는 값은 모두 피벗보다 작고, 피벗 오른쪽에 있는 값은 모두 피벗보다 크다고 확실할 수 이있다. 또한, 다른 값들은 아직 완전히 정렬되지 않았지만 피벗 자체는 이제 배열 내에서 올바른 위치에 있다는 뜻이다.

• 자바스크립트로 코드 구현

13.2 퀵 정렬

퀵 정렬 알고리즘은 분할과 재귀로 이뤄진다. 피벗을 기준으로 왼쪽과 오른쪽 하위 배열로 나눠 분할 과정을 거친다.

0	1	2	3	5	6
			피벗

먼저, 피벗 기준 왼쪽 하위 배열을 분할해보자.

1. 왼쪽 하위 배열의 가장 마지막 값이 2를 피벗으로 한다.

0	1	2
		피벗

2.피벗 앞의 숫자 왼쪽, 오른쪽 포인터를 설정한다.

0	1	2
↑	↑	피벗

3. 왼쪽 포인터(0)와 피벗(2)을 비교한다. 0은 피벗보다 작으므로 왼쪽 포인터를 옮긴다.

0	1	2
	↑ ↑	피벗

4. 왼쪽 포인터(1)와 피벗(2)을 비교한다. 1은 피벗보다 작으므로 왼쪽 포인터를 옮긴다.

0	1	2
	↑	↑ 피벗

5. 왼쪽 포인터(2)와 피벗(2)가 동일하므로 왼쪽 포인터를 멈춘다.

6. 이제 오른쪽 포인터를 동작시킨다. 오른쪽 포인터의 값(1)이 피벗보다 작으므로 그대로 둔다.

7. 왼쪽 포인터가 오른쪽 포인터를 지나쳤으므로 이번 분할에서 더이상 포인터를 이동시키지 않는다.

8. 피벗과 왼쪽 포인터의 값을 교환해야 되지만, 동일한 값(2)을 가리키고 있기 때문에 아무런 변화가 없다.

9. 왼쪽 하위 배열의 요소가 0또는 1개 남을 때까지 분할 과정을 반복한다.

10. 오른쪽 하위 배열의 분할 과정도 동일하다. 피벗(3)를 기준으로 오른쪽 하위 배열을 분할한다.

11. 가장 끝의 값을 피벗으로 정한다. 왼쪽, 오른쪽 포인터가 모두 6를 가리킨다.

6	5
↑ ↑	피벗

12. 왼쪽 포인터(6)과 피벗(5)를 비교한다. 6이 5보다 크기 때문에 포인터를 움직이지 않는다.

13. 오른쪽 포인터는 피벗보다 작은 값을 만났을 때까지 이동해야 되지만, 더이상 셀이 없으므로 오른쪽 포인터의 이동을 뭄춘다.

14. 두 포인터가 멈췄으므로 왼쪽 포인터와 피벗의 값을 교환한다. 피벗(5)가 올바른 위치에 놓여졌다.

15. 5의 오른쪽 하위 배열을 재귀적으로 분할해야 한다. 하지만, 원소가 하나(6) 이기 때문에 기저 조건을 충족해서 재귀를 종료한다.

13.3 퀵 정렬의 효율성

퀵 정렬의 효율성을 알아내려면 한 번 분할할 때의 효율성을 밝혀야 한다.
분할에 필요한 단계를 분류해 보면 2단계로 나눌 수 있다.

• 비교: 각 값과 피벗을 비교한다.
• 교환: 왼쪽, 오른쪽 포인터의 값을 교환한다.

비교 횟수는 각 분할마다 배열 내 각 원소를 피벗과 비교하므로 최소 N번 비교한다.

교환 횟수는 데이터가 어떻게 정렬되어 있는냐에 따라 다르다. 모든 값을 교환한다 해도 한 번에 두개의 값을 교환하므로 한 분할에 최대 N/2번 교환한다. 평균적으로 N/4번 정도 교환한다.

한 번 분할할 때의 효율성은 O(N)이라고 할 수 있다.

한눈에 보는 퀵 정렬

퀵 정렬은 각 분할마다 하위 배열의 원소가 N개 일 때, 약 N단계 걸린다.
결론적으로 모든 하위 배열의 크기를 합하면 퀵 정렬에 걸리는 총 단계 수가 나온다.

배열의 원소가 8개일 때 약 21단계가 걸렸다. 각 분할 후 피벗이 하위 배열의 중간 부근에 놓일 것이라는 평균적인 시나리오를 가정한 것이다.

원소가 16개인 배열에 대해 퀵 정렬 단계 수를 보면 다음과 같다.

N	퀵 정렬 단계 수(근사치)
4	8
8	24
16	64
32	160

빅 오로 나타낸 퀵 정렬

앞서 봤던 패턴을 보면 다음의 표에 나오듯이 배열의 원소가 N개일 때 퀵 정렬에 필요한 단계 수는 약 N * logN이다.

평균적인 시나리오에서 배열을 분할할 때마다 하위 배열 두 개로 나누면 이 두 배열의 크기는 비슷하다. 크기가 N인 배열을 크기가 1이 될때까지 각 하위 배열을 반으로 나누려면 logN번 걸린다. 각 하위 배열의 분할 횟수를 합치면 N단계가 걸린다.

하지만, O(N*logN)는 근사치이다. 정확한 단계를 나타내진 않는다.

N	logN	N*logN	퀵 정렬 단계 수 (근사치)
4	2	8	8
8	3	24	24
32	5	160	160

13.4 퀵 정렬의 최악의 시나리오

이전 가정은 평균적인 시나리오였다면, 최악의 시나리오는 피벗이 항상 배열의 끝에 있을 때다. 배열이 완전 오름차순 또는 내림차순일 때 일어날 수 있다.

원소가 N개 일 때, N + (N-1)+ ...+ 1단계가 걸린다. N^2/2단계이므로 빅 오로 O(N^2)이다.

퀵 정렬 대 삽입 정렬

	최선	평균	최악
삽입 정렬	O(N)	O(N^2)	O(N^2)
퀵 정렬	O(NlogN)	O(NlogN)	O(N^2)

평균적인 상황에서는 퀵 정렬이 효율적이기 때문에 퀵 정렬을 사용해서 내장 정렬 함수를 구현하는 언어가 많다.

13.5 퀵 셀렉트

13.6 다른 알고리즘의 핵심 역할을 하는 정렬

가장 빠른 정렬 알고리즘의 속도는 O(NlogN)이다. 배열의 중복 확인하는 문제에 정렬을 사용해서 더 효율적인 알고리즘을 만들 수 있다.

// 중복 확인 알고리즘

정렬 (NlogN) 단계와 배열 순회 N 단계가 걸려서 결과적으로 O(NlogN)이 된다. 원래 O(N^2)걸리던 알고리즘에서 O(NlogN)으로 개선할 수 있다.
정렬을 잘 사용하면 효율성을 크게 개선할 수 있겠다.