Solution >
빠른 정렬(Quick Sort)은 교환정렬의 일종이며 분할-정복법(divide and conquer)에 근거한다. 데이터를 하나의 축(pivot)값을 기준으로 정렬할 리스트를 두 개로 분할하고 정렬하는데, 축 값을 중심으로 축 값보다 큰 값은 오른쪽리스트에 작은 값은 왼쪽리스트로 이동시킨다.
오른쪽 리스트와 왼쪽 리스트부분은 독립적인 단위로 정렬하여 오른쪽 리스트부분에 대한 새로운 분할 축 값을 선택하여 두 부분으로 분리하고, 왼쪽 리스트부분 역시 새로운 축 값을 선택하여 두 부분으로 분리하는 과정을 반복하는데 리스트들은 재귀적 방법으로 각각 재배열하는 방식이다. 각 분할 자료개수가 1이 되면 완전히 정렬된 상태의 데이터가 구성된다.
빠른 정렬은 크게 (1) Pivoting, (2) Partitioning, (3) Recursive 의 세 과정으로 이루어진다.
Pivoting 과정은 pivot 값을 결정하는 단계이다. 빠른 정렬 알고리즘은 pivot 값을 잘 결정하여야 O(n•log n)의 시간 바운드가 결정된다. 이 pivot 값이 매 단계에서 최악으로 선택될 경우(제일 큰 값이나 제일 작은 값이 pivot이 되는 경우) 빠른 정렬 알고리즘은 O(n^2)으로 성능이 떨어져버린다. 이런 문제를 "bad partition" (파티션 과정 시 양쪽으로 균등하게 분배되지 않는 문제)이라고 부르며, "bad partition"이 발생할 경우 Heap Sort 로 정렬 전략을 수정하는 Intro Sort 라는 알고리즘이 현재 개발되어 있다. Intro Sort는 평균적으로 빠른 정렬 알고리즘만큼 빠르며(시간 복잡도가 동일한 Merge Sort 나 Heap Sort 는 계수가 커서 빠른 정렬 알고리즘보다 느리다.) "bad partition" 발생시 전략이 Heap Sort 로 수정되므로 항상 O(N log N)의 시간 복잡도를 보장하게 된다.
Pivoting 과정에는 여러 가지 방법이 있을 수 있겠지만, 주로 다음 4가지가 많이 쓰인다.
① 최초의 원소를 피벗으로 사용하는 방법
② 최후의 원소를 피벗으로 사용하는 방법
③ 중간 원소를 피벗으로 사용하는 방법
④ 최초, 중간, 최후의 원소 중 중앙값(median)을 사용하는 방법
최초의 원소를 피벗으로 사용하는 방법은 배열의 0 번째 키를 축 값으로 1 번째 키부터 시작해서 2, 3번 방향으로 축 값보다 큰 값을 가진 키를 만나면 그 키를 선택, n – 1 번째 키부터 시작 n - 2, n - 3번 방향으로 축 값보다 작은 값을 가진 키를 만나면 그 키를 선택하여 두 키의 값을 교환한다. 선택되었던 두 키의 다음 위치에서부터 동일한 과정을 반복하고 양쪽 방향에서 진행하는 순서가 교차하면 정지한다. 가장 나중에 선택한 기준 키 값보다 작은 키를 기준 키와 교환하는 방식이다. 최후의 원소를 피벗으로 사용하는 방법도 이와 동일하나 기준점이 n – 1 번째 키라는 것이 다르다.
중간 원소를 피벗으로 사용하는 방법은 데이터의 중간 위치에 있는 키의 값을 축 값으로 설정하는 방식으로 기준 키 값의 앞에서 축 값보다 큰 값을, 뒤에서 축 값보다 작은 값을 선택하여 교환한다.
최초, 중간, 최후의 원소 중 중앙값(median)을 사용하는 방법은 데이터의 최초, 중간, 최후의 원소가 가진 값을 비교하여 중앙값을 축 값으로 사용하는 방법으로 축 값이 결정되면 해결방법은 위에서 설명한 내용과 같다.
Partitioning 과정은 피벗 값을 기준으로 더 작은 원소는 왼쪽, 더 큰 원소는 오른쪽으로 분배하는 작업이다. 이 과정은 원소의 개수에 비례하여 시간이 걸린다. Partitioning 알고리즘도 stable 한 Partitioning 이 있고 unstable 한 Partitioning 이 있는데 일반적으로 unstable 한 알고리즘이 속도가 빠르기 때문에 주로 그것을 사용한다. Stable 한 정렬 알고리즘이 필요할 때는 주로 빠른 정렬보다는 병합 정렬을 사용한다.
Partitioning 과정이 끝나면 각각의 좌측 리스트, 우측 리스트에 대해 재귀적으로 동일하게 빠른 정렬 알고리즘을 적용한다. 재귀 호출(Recursive)의 깊이는 매 파티션에서 리스트가 균등하게 반정도로 나눠진다고 가정할 경우 log N단계 정도가 된다.
최초의 원소를 피벗으로 사용하는 방법은 이미 많이 알려져있고, 가장 흔하게 찾아볼 수 있으므로 이 글에서는 중간 원소를 피벗으로 사용하는 방법으로 문제를 해결하였다.
입력 데이터는 1 부터 500 사이의 정수 값들을 임의의 난수로 발생시켜 저장한 input.txt 파일을 불러들여 사용하였다. Input.txt 파일이 없을 때에는 입력 데이터를 만들 수 있도록 1 부터 500 사이의 난수를 발생시켜 파일로 저장하는 makefile() 함수를 구현해놓았다. 이 함수는 input.txt 파일에 저장된 데이터가 없을 때에도 사용된다.
Time Complexity >
ㆍ 최선일 경우의 비교회수 공식 : n - 1
ㆍ 최악일 경우의 비교회수 공식 : n(n – 1)/2
제일 처음에는 (n – 1)번을 비교하고, 그 다음에는 (n – 2)번 만큼 비교하고, 그 다음은 (n – 3)번을 비교하면서 비교회수가 1이 될 때까지 이 작업을 반복할 것이다. 그러므로 총 비교회수는 (n – 1) + (n – 2) + (n – 3) …… + 1 이 될 것이다. 최대 (n – 1)번을 수행할 것이며, 각 패스가 수행할 때마다 수학식으로 표현하면 ∑(i = 1 ~ n - 1)〖n - 1〗 이므로 공식은 n(n – 1)/2 이런 공식이 성립된다.
ㆍ 평균 비교횟수가 n•Log2n => O(n•Log n)
T(n) ≤ cn + 2T(n / 2)
≤ cn + 2(c x n / 2 + 2T(n / 4)) = 2cn + 4T(n / 4)
≤ 3n + 8T(n / 8)
≤ 4n + 16T(n / 16)
ㆍ 최악의 경우(서브파일이 하나만 존재) => O(n^2)
Example >
|
Pivot = list[(0 + 11) / 2] = 25, Left = 0, Right = 11 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
34 |
22 |
44 |
11 |
22 |
25 |
21 |
9 |
55 |
31 |
16 |
6 |
|
→ |
|
|
|
|
|
|
|
|
|
|
← |
|
Pivot = 25, Left = 0, Right = 11 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
34 |
22 |
44 |
11 |
22 |
25 |
21 |
9 |
55 |
31 |
16 |
6 |
|
Left |
|
|
|
|
|
|
|
|
|
|
Right |
|
Pivot = 25, Left = 0, Right = 11 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
22 |
44 |
11 |
22 |
25 |
21 |
9 |
55 |
31 |
16 |
34 |
|
|
|
Left |
|
|
|
|
|
|
|
Right |
|
|
Pivot = 25, Left = 2, Right = 10 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
22 |
16 |
11 |
22 |
25 |
21 |
9 |
55 |
31 |
44 |
34 |
|
|
|
|
|
|
Left |
|
Right |
|
|
|
|
|
Pivot = 25, Left = 5, Right = 7 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
22 |
16 |
11 |
22 |
9 |
21 |
25 |
55 |
31 |
44 |
34 |
|
low |
|
|
|
|
|
Right |
Left |
|
|
|
high |
|
Pivot = 25, Left = 7, Right = 6 | Left 와 Right 가 교차, low-right, left-high로 분할 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
22 |
16 |
11 |
22 |
9 |
21 |
25 |
55 |
31 |
44 |
34 |
|
Left |
|
|
Pivot |
|
|
Right |
Left |
|
Pivot |
|
Right |
|
Pivot = 11, Left = 0, Right = 6 | Pivot = 31, Left = 7, Right = 11 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
22 |
16 |
11 |
22 |
9 |
21 |
25 |
55 |
31 |
44 |
34 |
|
|
Left |
|
|
|
Right |
|
|
Left |
Right |
|
|
|
Pivot = 11, Left = 1, Right = 5 | Pivot = 31, Left = 8, Right = 9 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
9 |
16 |
11 |
22 |
22 |
21 |
25 |
31 |
55 |
44 |
34 |
|
|
|
Left |
Right |
|
|
|
|
Right |
Left |
|
|
|
Pivot = 11, Left = 2, Right = 3 | Pivot = 31, Left = 8, Right = 9 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
9 |
11 |
16 |
22 |
22 |
21 |
25 |
31 |
55 |
44 |
34 |
|
|
L, R |
|
|
L |
|
R |
L, R |
|
L |
|
R |
|
Pivot = 9, 22, 25, 44 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
9 |
11 |
16 |
21 |
22 |
22 |
25 |
31 |
34 |
44 |
55 |
|
|
|
|
L, R |
|
L, R |
|
|
|
|
|
|
|
Pivot = 16, 22 | |||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
6 |
9 |
11 |
16 |
21 |
22 |
22 |
25 |
31 |
34 |
44 |
55 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Before Sorting, entries of list[] are :
|
34 |
22 |
44 |
11 |
22 |
25 |
21 |
9 |
55 |
31 |
16 |
6 |
After sorting, entries of list[] are :
|
6 |
9 |
11 |
16 |
21 |
22 |
22 |
25 |
31 |
34 |
44 |
55 |
Source >
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#define MAX 50 // 여기서는 임의의 난수 50개가 저장된 파일에서 데이터를 입력받는다.
void quicksort(int list[], int low, int high);
void swap(int *m, int *n);
void makefile(int m);
int main(int argc, char* argv[])
{
int i, count, temp;
int *list;
FILE *fr;
// input.txt 파일이 없을 경우
if ((fr = fopen("input.txt", "r")) == NULL)
{
printf("Can't open File. Create 'input.txt' File.\n\n");
makefile(MAX);
fr = fopen("input.txt", "r");
}
// input.txt 파일에 있는 데이터의 갯수를 count
for (count = 0; (fscanf(fr, "%d", &temp)) != EOF; count++);
// input.txt 파일에 데이터가 없을 경우
if(count == 0)
{
printf("'input.txt' has not Data. Create 'input.txt' File.\n\n");
makefile(MAX);
for (count = 0; (fscanf(fr, "%d", &temp)) != EOF; count++);
}
rewind(fr);
// input.txt 에서 읽은 데이터의 갯수만큼 list 배열에 동적 메모리 할당
list = (int *)malloc(sizeof(int) * count);
// 입력은 테스트할 데이터가 저장된 파일(50개의 데이터)로부터 받는다.
printf("---------------- Before sorting, the entries of list[] are -----------------\n");
for (i = 0; (fscanf(fr, "%d", &list[i])) != EOF && i < count; i++)
{
printf("%3d\t", list[i]);
if(((i + 1) % 10) == 0)
printf("\n");
}
printf("\n");
// quicksort() 호출
quicksort(list, 0, count - 1);
// 출력은 표준출력장치에 보여준다(한 줄에 열 개씩).
printf("---------------- After sorting, the entries of list[] are ------------------\n");
for (i = 0; i < count; i++)
{
printf("%3d\t", list[i]);
if(((i + 1) % 10) == 0)
printf("\n");
}
free(list);
fclose(fr);
return 0;
}
void quicksort(int *list, int low, int high)
{
int left, right, pivot;
left = low;
right = high;
// pivotitem 으로 list[]의 중간 아이템을 선택
pivot = list[(left + right) / 2];
while(left <= right)
{
while(list[left] < pivot) left++;
while(list[right] > pivot) right--;
if(left <= right)
{
swap(&list[left], &list[right]);
left++;
right--;
}
}
if(right > low) quicksort(list,low,right);
if(left < high) quicksort(list,left,high);
}
void swap(int *m, int *n)
{
int temp;
temp = *m;
*m = *n;
*n = temp;
}
// 테스트할 데이터가 저장된 "input.txt" 파일이 없을 경우 생성해주는 함수
void makefile(int m)
{
int i;
FILE *fw;
fw = fopen("input.txt", "w");
srand(time(NULL));
for(i = 0; i < m; i++)
fprintf(fw, "%3d\t", rand() % 500 + 1);
fclose(fw);
}Input.txt >
321 9 448 331 33 60 461 28 18 424
339 153 325 177 493 376 436 30 308 61
378 291 22 49 248 218 366 400 364 441
427 196 400 117 213 440 334 399 70 124
134 54 153 362 469 273 6 164 278 272Result >
