[알고리즘] 퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)…

이름처럼 빠르다고 한다.

 

퀵 정렬은 분할 정복(Divide and Conquer)에 기반되어 있다.

전체를 공략하는 대신 전체를 구성하는 구성 요소들을 잘게 나누어 쪼갠 적을 공략하는 기법이다.

 

퀵 정렬은 다음과 같이 정렬을 수행한다.

1. 데이터 집합 내에서 임의의 기준을 선택하고 기준보다 작은 것은 순서에 관계 없이 기준의 왼쪽에 큰 것은 오른쪽에 위치
2. 이렇게 나눈 데이터를 위에서와 같이 임의의 기준을 다시 선택하고 같은 방법으로 데이터를 분할 한다.
3. 1과 2를 더 이상 나눌 수 없을 때 까지 반복 하면 정렬이 완성 된다.

6				4				2				3				1				5
↑기준				→																←
6				4				2				3				1				5
↑기준								→												←
6				4				2				3				1				5
↑기준												→								←
6				4				2				3				1				5
↑기준																→				←
6				4				2				3				1				5
↑기준																				→ ←

기준을 6으로 잡고 Left와 Right를 비교해본다.

그러나 6이 최고로 큰 수 이므로 5와 6을 자리 교환 한다.

 

5				4				2				3				1				6
↑기준				→												←
5				4				2				3				1				6
↑기준								→								←
5				4				2				3				1				6
↑기준												→				←
5				4				2				3				1				6
↑기준																→ ←

5를 기준으로 비교를 해본다

하지만 6과 똑같이 최고로 큰 수이므로 1과 자리를 교환 한다.

 

1		4		2		3		5		6
↑기준		→				←
1		4		2		3		5		6
↑기준		→		←
1		4		2		3		5		6
↑기준		→ ←

1을 기준으로 비교 해본다.

1은 남은 숫자들 중에서 제일 작은 숫자 이므로 제 자리를 차지하고 있는다.

 

1	4	2	3	5	6
	↑기준	→	←
1	4	2	3	5	6
	↑기준		→ ←

4를 기준으로 비교 해본다.

2는 4보다 작고 3도 4보다 작으므로 4는 3과 자리 교환을 하게 된다.

 

1	3	2	4	5	6
	↑기준	→ ←

3을 기준으로 비교를 해본다. 그러나 남은 숫자는 2 뿐이다.

3과 2를 비교했을 때 2가 3보다 작으므로 3과 2를 자리 교환한다.

1	2	3	4	5	6

이로써 퀵 정렬이 마친 상태이다.

 

퀵 정렬의 성능을 분석 시 다음과 같은점을 알아야 한다.

• 퀵 정렬의 재귀 호출의 깊이
• 데이터 집합을 나누기 위해 필요한 비교 횟수

 

이 점을 염두하고 성능을 살펴 보자.

 

먼저 이상적인 경우와 최악의 경우를 살펴보자

 

이상적인 경우는 다음과 같다.

퀵 정렬이 한번 호출 할 때마다 1/2씩 쪼개질 경우이다.

 

1 , 2 , 4 , 8 , 16 , 32 …

이렇게 한 덩어리를 한 번에 두 조각으로 나누고 그 두 조각이 네 조각이 되고 ….

여기서 나오는 규칙은 다음과 같다.

 

데이터 집합의 크기가 n개일 때 퀵 정렬의 재귀 호출 깊이는 이다.

 

퀵 정렬의 비교 횟수는 다음과 같다.

1회 에서 n 회

2회에서 n/2 + n/2 = n 회

3회에서 n/4 + n/4 + n/4 + n/4 = n회

    ....

n회 n/n + n/n + … n/n + n/n = n회

 

 

이와 같은 결과로 가장 이상적인 경우에서의 퀵 정렬의 성능은 다음과 같다.

 

 

그리고 최악의 경우를 살펴 보자..

 

다음 그림과 같이 재귀 호출 시 마다 분할이 1:n-1 로 이루어 질 때 이다.

 

이렇게 되면 재귀 호출의 깊이는 n-1 이 되고 호출 때 마다 범위도 1씩 줄어든다.

 

그러므로 …

 

이러한 결과가 나온다.

 

위의 결과는 최악의 경우일 때 성능이며 버블정렬이나 삽입 정렬의 성능과 비슷해진다.

 

 책의 내용과 유투브에 있는 동영상을 보면서

흔히 널려있는 퀵정렬 소스와는 다르게 짜본다고 했다가

괜시리 멘붕만 와서 오랜 시간이 걸렸다 .. ㅠㅠ