<재귀 : pivot을 배열의 중간값으로>
void qsort(int a[], int left, int right)
{
int p, t;
int i, j;
if( left < right) {
p = a[(left + right) / 2];
i = left - 1;
j = right + 1;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
qsort(a, left, i-1);
qsort(a, j+1, right);
}
}
{
int p, t;
int i, j;
if( left < right) {
p = a[(left + right) / 2];
i = left - 1;
j = right + 1;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
qsort(a, left, i-1);
qsort(a, j+1, right);
}
}
<재귀 : pivot을 배열의 첫 번째 값으로>
void qsort(int a[], int left, int right)
{
int p, t;
int i, j;
if( left < right) {
p = a[left];
i = left;
j = right + 1;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
/* pivot 값을 교환 */
a[left] = a[j];
a[j] = p;
qsort(a, left, j-1);
qsort(a, j+1, right);
}
}
{
int p, t;
int i, j;
if( left < right) {
p = a[left];
i = left;
j = right + 1;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
/* pivot 값을 교환 */
a[left] = a[j];
a[j] = p;
qsort(a, left, j-1);
qsort(a, j+1, right);
}
}
** 재귀 함수의 문제점
배열이 아주 클 경우 스택 오버플로우가 발생할 위험
--> 자체 스택을 만들어 비재귀하는 방식으로 개선
--> 구간이 작을 경우 더 이상 재귀 호출을 하지 말고 선택 정렬이나 삽입 정렬 이용
<비재귀 함수>
#include <stdio.h>
#define MAX_NUM 50
#define MAX_NUM 50
int stack[MAX_NUM];
int top = 0;
void init_stack()
{
top = 0;
}
void push(int i)
{
if( top >= MAX_NUM) {
printf("stack full\n");
return;
}
else
stack[top++] = i;
}
int pop()
{
if( top == 0)
return 0;
else
return stack[--top];
}
int is_stack_empty()
{
if( top == 0)
return 1;
else
return 0;
}
int top = 0;
void init_stack()
{
top = 0;
}
void push(int i)
{
if( top >= MAX_NUM) {
printf("stack full\n");
return;
}
else
stack[top++] = i;
}
int pop()
{
if( top == 0)
return 0;
else
return stack[--top];
}
int is_stack_empty()
{
if( top == 0)
return 1;
else
return 0;
}
void qsort(int a[], int n)
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 1) { // 종료조건 :: 남아 있는 분할의 원소 개수가 1개 이상일 경우
p = a[r];
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
// pivot과 i값을 교환
t = a[i];
a[i] = a[r];
a[r] = t;
push(r); // 오른쪽 분할의 오른쪽 끝
push(i+1); // 오른쪽 분할의 왼쪽 끝
push(i-1); // 왼쪽 분할의 오른쪽 끝
push(l); // 왼쪽 분할의 왼쪽 끝
} // if
} // while
}
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 1) { // 종료조건 :: 남아 있는 분할의 원소 개수가 1개 이상일 경우
p = a[r];
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
// pivot과 i값을 교환
t = a[i];
a[i] = a[r];
a[r] = t;
push(r); // 오른쪽 분할의 오른쪽 끝
push(i+1); // 오른쪽 분할의 왼쪽 끝
push(i-1); // 왼쪽 분할의 오른쪽 끝
push(l); // 왼쪽 분할의 왼쪽 끝
} // if
} // while
}
** 비재귀 함수의 문제점
재귀함수에 비해 실행시간이 약간 빠르다. 그러나, push(), pop()을 사용하므로 함수호출에 의한 오버헤드
현상으로 속도가 확 달라지지는 않는다.
정렬된 배열과, 역순 배열에서는 그 속도가 40배 가량 느리다. ( O(n^2) )
?? 가장 큰 값이나 가장 작은 값이 pivot으로 되기 때문에 속도 저하
--> pivot 값을 난수로 지정하는 방법
< 난수 발생>
int get_random(int range)
{
return rand() % range;
}
void qsort3(int a[], int n)
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 1) {
t = get_random(r-l+1) + l; // 난수 발생
p = a[t];
a[t] = a[r];
a[r] = p;
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[i];
a[i] = a[r];
a[r] = t;
push(r);
push(i+1);
push(i-1);
push(l);
} // if
} // while
}
{
return rand() % range;
}
void qsort3(int a[], int n)
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 1) {
t = get_random(r-l+1) + l; // 난수 발생
p = a[t];
a[t] = a[r];
a[r] = p;
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[i];
a[i] = a[r];
a[r] = t;
push(r);
push(i+1);
push(i-1);
push(l);
} // if
} // while
}
이 경우는 최악의 경우가 발생하지 않는다.
<삽입정렬 추가>
void insert_sort(int a[], int n)
{
int i, j, t;
for( i = 1; i < n; i++) {
t = a[i];
j = i;
while( a[j-1] > t && j > 0) {
a[j] = a[j-1];
j--;
}
a[j] = t;
}
return;
}
void qsort4(int a[], int n)
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 200) {
t = get_random(r-l+1) + l; // 난수 발생
p = a[t];
a[t] = a[r];
a[r] = p;
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
{
int i, j, t;
for( i = 1; i < n; i++) {
t = a[i];
j = i;
while( a[j-1] > t && j > 0) {
a[j] = a[j-1];
j--;
}
a[j] = t;
}
return;
}
void qsort4(int a[], int n)
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 200) {
t = get_random(r-l+1) + l; // 난수 발생
p = a[t];
a[t] = a[r];
a[r] = p;
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[i];
a[i] = a[r];
a[r] = t;
push(r);
push(i+1);
push(i-1);
push(l);
} // if
else
insert_sort(a+l, r-l+1);
} // while
}
a[i] = a[r];
a[r] = t;
push(r);
push(i+1);
push(i-1);
push(l);
} // if
else
insert_sort(a+l, r-l+1);
} // while
}
삽입 정렬은 어느 정도 정렬된 배열에서 아주 큰 효과를 내기 때문에 사용...
메모리의 소모도 줄어듬...
<세 값의 중위>
void qsort4(int a[], int n)
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 200) {
t = (r+1) >> 1; // 나누기 2의 의미
if( a[l] > a[t]) {
p = a[l];
a[l] = a[t];
a[t] = p;
}
if( a[l] > a[r]) {
p = a[l];
a[l] = a[r];
a[r] = p;
}
if( a[t] > a[r]) {
p = a[t];
a[t] = a[r];
a[r] = p;
}
p = a[t];
a[t] = a[r-1];
a[r-1] = p;
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
{
int p, t;
int i, j;
int l, r;
init_stack();
l = 0;
r = n - 1;
push(r);
push(l);
while(!is_stack_empty()) {
l = pop();
r = pop();
if( r-l+1 > 200) {
t = (r+1) >> 1; // 나누기 2의 의미
if( a[l] > a[t]) {
p = a[l];
a[l] = a[t];
a[t] = p;
}
if( a[l] > a[r]) {
p = a[l];
a[l] = a[r];
a[r] = p;
}
if( a[t] > a[r]) {
p = a[t];
a[t] = a[r];
a[r] = p;
}
p = a[t];
a[t] = a[r-1];
a[r-1] = p;
i = l - 1;
j = r;
while(1) {
while(a[++i] < p);
while(a[--j] > p);
if( i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[i];
a[i] = a[r];
a[r] = t;
push(r);
push(i+1);
push(i-1);
push(l);
} // if
else
insert_sort(a+l, r-l+1);
} // while
}
a[i] = a[r];
a[r] = t;
push(r);
push(i+1);
push(i-1);
push(l);
} // if
else
insert_sort(a+l, r-l+1);
} // while
}
* 복잡도
- Best Case
T(n) = n + 2T(n/2)
= n + 2(n/2 + 2T(n/4)) = 2n + 4T(n/4)
= ...
= n log n
- Worst Case
T(n) = n + T(n-1)
= n + (n-1) + T(n-2)
= ...
= O(n^2)
'IT > 알고리즘' 카테고리의 다른 글
| + integer 값을 - integer 값으로 바꾸는 가장 간단한 방법 (0) | 2008.07.16 |
|---|---|
| 하나의 소수(솟수)가 주어졌을때, 다음 소수(솟수)를 찾는 알고리즘 (0) | 2008.07.15 |
| 스트링에 대한 permutation을 구하는 알고리즘 (0) | 2008.07.15 |
| mmap (메모리맵) (0) | 2008.07.08 |
| 피보나치 수열 (2) | 2008.07.08 |
쩐의시대
나답게 살아가고 나답게 살아가자