드디어 고급 정렬에 들어왔습니다.
이번에는 고급 정렬 알고리즘 중 하나인 퀵 정렬에 알아보도록 하겠습니다.
취업을 위해 알고리즘 문제를 풀게 되는데, 정렬은 이러한 문제를 푸는 데 많이 사용됩니다.
저도 문제를 풀다가 정렬을 해야할 경우 퀵 정렬을 많이 사용하곤 합니다. (왜냐하면 이름처럼 빠르기 때문이죠!)
그럼 이제부터 본격적으로 퀵 정렬에 파헤쳐 보도록 하겠씁니다.
퀵 정렬(Quick sort) - 불안정 정렬(Unstable sort)
퀵 정렬은 전체를 분할 중심보다 작은 구간, 큰 구간 으로 나누는 작업을 재귀적으로 수행하여 정렬하는 알고리즘입니다.
즉, 분할 정복 기법을 활용하는 방법입니다.
동작 하는 과정은 다음과 같습니다.
1) 분할 중심(Pivot)값 을 정합니다.
(분할 중심을 정하는 방법은 여러 가지가 있는데, 저는 마지막 원소를 분할 기준으로 정하는 방법을 사용하도록 하겠습니다.)
2) 주어진 데이터 구간을 분할 중심을 기준으로 대소 관계에 따라 두 구간으로 나눕니다.
3) 분할된 구간 중 기준 값보다 큰 구간의 첫 번째 값과 분할 중심 값을 교환합니다.
4) 나누어진 두 구간 각각에 대해서 1~3 번 과정을 반복(혹은 재귀적)으로 수행합니다.
이렇게 나누고 정렬하는 작업을 분할할 공간이 없을 때 까지 진행하면 정렬은 끝입니다!
소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include <cstdio> #define SWAP(x,y,temp) ((temp)=(x),(x)=(y),(y)=(temp)) //분할 int partion(int * a, int left, int right) { //마지막 값을 분할 기준으로 설정 int pivotValue = a[right]; int temp; int i = left; //주어진 구간을 탐색하며 두 구간으로 분리 for (int j = left; j < right; j++) { if (a[j] < pivotValue) { SWAP(a[j], a[i], temp); i++; } } //작은 구간과 큰 구간 사이에 분할기준 삽입 SWAP(a[i], a[right], temp); return i; } //퀵 정렬 void quicksort(int * a, int left, int right) { int newPivotIndex; if (right > left) { //분할의 결과로 a배열은 pivot을 기준으로 좌측에는 작은 값 우측에는 큰 값이 위치 newPivotIndex = partion(a, left, right); //작은 구간에 대해서 재귀적으로 퀵 정렬 진행 quicksort(a, left, newPivotIndex - 1); //큰 구간에 대해서 재귀적으로 퀵 정렬 진행 quicksort(a, newPivotIndex + 1, right); } } int main() { int a[7] = { 7,3,2,1,5,4,6 }; quicksort(a, 0, 6); for (int i = 0; i < 7; i++) printf("%d ", a[i]); return 0; } | cs |
시간 복잡도
우선, 앞서 설명했던 알고리즘 들과 같이 최악의 경우를 고려한 시간 복잡도를 말씀 드리겠습니다.
퀵 정렬에서 최악의 경우는 분할 기준이 매번 제일 크거나 작은 값으로 선택되는 상황입니다.
다시 말해, 이미 정렬된 데이터에 대해서 퀵 정렬을 수행하는 경우입니다.
이럴 때, 분할은 결국 N-1 번 발생하고 각 분할당 최소 1번부터 최대 N-1 번까지 비교하게 됩니다.
그렇게 된다면 결국 퀵정렬의 최악의 경우는 
그럼에도 퀵 정렬을 사용하는 포인트는 다음과 같습니다.
1) 평균적인 경우를 고려하자!
우선 분할의 가장 이상적인 경우는 반반씩 나뉘는 것입니다.
다시 말해, 매 분할마다 정렬해야할 데이터의 크기가 반씩 줄어든다는 의미입니다.
따라서 그럴 경우에는 
이런 경우에는 분할 깊이 * 비교 횟수인 
2) 분할 기준이 다음 정렬의 대상이 아니다!
퀵 정렬의 경우에는 분할 기준이 다음 정렬에서 정렬 대상이 포함되지 않습니다.
그렇기 때문에,
왜 불안정 정렬인가?
선택 정렬이 불안정 정렬임을 보였을 때 처럼 아주 간단한 예시를 보여드리겠습니다.
(이번에도 제가 자주 사용하는 카드를 통해서 알아보겠습니다!)
우선 아래와 같이 스페이스3 - 하트5 - 클로버5 있다고 생각해 봅시다!
원본 데이터가 정렬되어 있지만, 보통 우리는 데이터가 정렬되있다고 판단하기 어렵습니다.
그렇기 때문에 데이터의 정렬 상태를 파악하지 않고 정렬을 진행하게 되는 것이죠!
이제 위 카드를 퀵 정렬 수행하게 된다면, 작은 구간(스페이스 3) / 큰 구간(하트 5) /정렬기준(클로버 5) 분리 됩니다.
그리고 나서 분할 기준(클로버 5)을 큰 구간의 첫 번째 값(하트 5)과 교환하게 됩니다.
교환 후에, 재귀적으로 수행하기 위해서 인덱스 위치를 살펴보니 더 이상 정렬할 구간이 없으므로 종료하게 됩니다.
결과를 살펴보면 기존에는 숫자 5를 가진 카드는 하트5 - 클로버5 순서로 존재했지만,
정렬 후에는 클로버 5 - 하트 5 순서로 존재함을 확인 할 수 있습니다.
따라서 퀵 정렬은 불안정 정렬이 됩니다.
여기서 추가적으로 분할 기준을 다르게 잡으면 가능할까? 라는 생각을 가지신 분들이 있을 수도 있습니다.
하지만, 퀵 정렬의 경우에는 분할 기준과의 값에 대한 교환이 필연적으로 나올 수 밖에 없기 때문에 불안정 정렬이 됩니다.
퀵 정렬에 대한 내용은 여기까지입니다! 다음 포스팅에서는 퀵 정렬과 가장 많이 비교되는 병합 정렬에 대해서 알아보겠습니다!
개인적인 일 때문에 이번 포스팅이 많이 늦어졌는데 다음 포스팅 부터는 최대한 노력해서 빨리 올려볼게요!
감사합니다 : )
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] - 그래프의 표현 방법 #8 (0) | 2019.03.13 |
|---|---|
| [알고리즘] - 합병 정렬(Merge sort) #7 (2) | 2019.02.06 |
| [알고리즘] - 선택 정렬(Selection sort) #5 (0) | 2019.01.16 |
| [알고리즘] - 삽입 정렬(Insertion sort) #4 (3) | 2019.01.15 |
| [알고리즘] - 버블 정렬(Bubble Sort) #3 (1) | 2019.01.10 |
