Algorithm #1. Sort algorithm. - 1.4 Quick Sort algorithm.

네. 저번주에 포스팅 하는 걸 잊었습니다.

... 그래서 이제부터 일주일 내내 하나씩 포스팅하기로 약속했습니다.
- Matrix 때문에 지금 Dlbo 군에게 열심히 갈굼당하고 있습니다. -_- 이건 그것도 겸한거죠. -

큼... 각설하고.

이번 포스팅 주제는 Quick Sort 알고리즘입니다.

정렬 알고리즘 중 가장 효율적이고 사용 빈도가 높은 알고리즘 중 하나입니다.
- C 언어 라이브러리 함수로 qsort() 라는게 있습니다. Quick Sort 를 라이브러리화 해 놓은 거라
  쉽게 사용이 가능합니다. 이것도 이유가 될 수 있겠죠. 비교 함수만 하나 더 만들어 주면 끝이거든요. -

흠... 일단 Quick Sort 를 소개하려면 'Divide and conquer' 라는 알고리즘 기법부터 설명해야 할까요.

'재귀' 라는 말은 한번쯤 들어 보셨겠죠?

쉽게 말해 자기 자신과 같은 일을 몇 번이고 계속 하는 구조를 일컬어 '재귀 구조' 라 합니다.

보통 '재귀'라 하면 재귀 함수를 생각하시는 분들이 많을 겁니다.

하지만, 여기서 말하고자 하는 재귀 구조는 '재귀 함수' 가 아닙니다.
- 물론, 우리가 Quick Sort를 구현할 때 재귀 함수를 쓰긴 합니다. -

단지 방법론적인 측면의 이야기를 하고 있죠.

즉, 주어진 문제를 해결하기 위해 전체의 큰 틀을 상정하고, 전체와 유사한 구조를 가지는 작은 틀들로
이 문제를  쪼갭니다.

그 후 재귀 구조를 이용, 이 작은 틀들을 기준으로 문제를 풀고, 다시 재결합하는 것이죠.

이 작은 틀은 전체 구조와 거의 유사한 구조를 가지고 있으므로, 이들을 '해결한다.' 라는 의미는
'전체 문제를 해결한다.' 라는 말과 같은 뜻이 될 겁니다.

이것이 분할 정복 - Divide and conquer - 기법이죠.

Quick Sort 알고리즘은 이 Divide and conquer 기법의 대표적인 예입니다.

자, 이제 알고리즘 소개를 해 볼까요.

1. 배열의 기준치를 잡는다.

2. 기준치를 중심으로 기준치보다 작은 수들은 왼쪽 배열에 대입한다.

3. 기준치를 중심으로 기준치보다 큰 수들은 오른쪽 배열에 대입한다.

4. 왼쪽 배열에 대해 1. 2 . 3 번 알고리즘을 계속 반복한다.

5. 더이상 바꿀 수가 없다면 오른쪽 배열에 대해 탐색한다.

6. 오른쪽 배열에 대해 1. 2. 3번 알고리즘을 반복한다.

7. 더이상 바꿀 수가 없다면. -> 정렬 종료.

한 눈에 보기에도 재귀 구조가 존재한다는 것을 알 수 있으실 겁니다.

알고리즘의 소개가 끝났으니, 소스 코드를 써 볼까요.

직접 구현을 할 수도 있겠지만, 일단은 라이브러리 함수를 사용하겠습니다.
혹시 Quick Sort 의 구현을 보고 싶으시다면 알려주세요.

#include <stdio.h> /* qsort() 라이브러리 함수의 호출을 위해 필요한 헤더 파일입니다. */ #include <stdio.h> /* qsort() 라이브러리 함수의 호출을 위해 필요한 헤더 파일입니다. */ #include <stdlib.h> /* 정렬할 배열입니다. */ int input[10]; /* 라이브러리 함수의 사용에 필요한 비교함수입니다. */ int compare(const void* a , const void* b) { /* 오름차순 정렬을 위해서 필요한 코드입니다. */ return *(int*)a - *(int*)b; } int main() { int i; for(i=0 ; i<10 ; i++) { printf("[%d]번째 수 입력 : ", i + 1); scanf("%d", &input[i]); } /* qsort() 함수를 호출합니다. */ qsort((void*)input, 10, sizeof(int), compare); for(i=0 ; i<10 ; i++) { printf("%4d", input[i]); } printf("\n"); return 0; }

이제까지처럼 10개의 레코드를 정렬하는코드입니다.

qsort 함수의 호출을 위해서는 인자 4개를 넘겨줘야 합니다. 순서대로 나열하죠.

qsort 라이브러리 함수.

- 포함 헤더파일.

stdlib.h


- 호출인자.

1.정렬할 배열.

2. 정렬할 배열의 크기.

3. 정렬할 배열의 데이터 크기.
- sizeof 함수를 이용합시다. -

4. 비교함수 식별자.
-사용자가 만들어 줍니다. 만약 위 코드와 달리 내림차순 정렬을 하고 싶다면 다음과 같이 비교함수를 만들어 주시면 됩니다. -
int compare(const void* a , const void* b) { return *(int*)b - *(int*)a; }

이제 성능 분석입니다.

직접 구현을 해 보면 아시겠지만, Quick Sort 는 기준치를 어떻게 잡냐에 따라 성능이 차이가 납니다.

일반적으로 가장 최악의 성능을 가질 때는 기준치가 각 케이스별로 배열의 first index 이거나 last index 일 경우입니다.
이 경우 평균 O(N^2) 의 시간복잡도를 가지게 된다는 것이 알려져 있습니다.

물론 최악의 경우만 놓고 보면 앞서 언급했던 알고리즘들과 성능차가 크게 나지 않습니다.

하지만 라이브러리 함수는 세 값의 중위법 - Three of Median - 을 이용합니다.
- 세 값의 중위법이란 배열의 first index 와 last index, 그리고 이 값의 중간값인 (first + last) / 2 의 세 값을 이용한 기법이죠. -
이 경우엔 분할이 거의 중앙에서 이루어지므로 재귀의 깊이가 대폭 줄어들게 됩니다.
평균적으로 O(N * log N)  의 시간복잡도를 갖게 되죠.

그러므로, 일반적으로 Quick Sort, 특히 라이브러리 함수를 이용하게 되면 시간복잡도 상한 O(N * log N)의
시간 안에 효율적으로 정렬을 할 수 있다는 것을 알 수 있습니다.