2007년 10월 04일
QuickSort 의 구현.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(x,y,t) ((t=x),(x=y),(y=t))
#define INPUT_SIZE 8000
int input[INPUT_SIZE];
int input_sort[INPUT_SIZE];
void quick_sort(int input[],int left, int right);
/*
void qsort(void *base,size_t nelem, size_t width,
int(*fcmp)(const void*, const void *));
base : 정렬 데이터 테이블의 선두번지
nelem : 정렬 할 할목 개수
width : 정렬할 데이터 크기
fcmp : 정렬에 사용될 비교함수.
*/
int sorting(const void *a, const void *b)
{
void main()
{
void quick_sort(int input[], int left, int right)
{
int pivot,i,j,tmp;
if(left < right)
{}
stdlib 에서 제공해주는 qsort() 함수와 교수님이 쓰시던 함수를 비교해서 속도를 재봤더니 신기하게도 교수님이 쓰시던게 더 빠르다고 나왔다. 모 책에서 보기론 qsort가 더럽게 빠르다고 해서 내심 기대하고 있었는데 거의 2배정도 차이난다. 하지만 문제는 재귀판인 교수님 소스는 데이터가 80만개가 넘어가면 행복한 에러를 내시고 사망.
하지만 qsort는 죽지않았다.
비재귀판인걸까? 그런데 속도는 더 느리다. 일반적으로 그게 가능한가?
그럴수도 있다고 생각되긴 하는데 교수님 말로는 재귀가 비재귀판보다 더 느리다고 하신다.
피보나치 수열 해결 알고리즘의 경우엔 이해가 가는데... 흠;;
#include <stdlib.h>
#include <time.h>
#define SWAP(x,y,t) ((t=x),(x=y),(y=t))
#define INPUT_SIZE 8000
int input[INPUT_SIZE];
int input_sort[INPUT_SIZE];
void quick_sort(int input[],int left, int right);
/*
void qsort(void *base,size_t nelem, size_t width,
int(*fcmp)(const void*, const void *));
base : 정렬 데이터 테이블의 선두번지
nelem : 정렬 할 할목 개수
width : 정렬할 데이터 크기
fcmp : 정렬에 사용될 비교함수.
*/
int sorting(const void *a, const void *b)
{
int t=0;
t = *(int *)a - *(int *)b;
if(t > 0 )return 1;
else if(t < 0)return -1;
else return 0;
} t = *(int *)a - *(int *)b;
if(t > 0 )return 1;
else if(t < 0)return -1;
else return 0;
void main()
{
int x;
int left = 0, right = INPUT_SIZE-1;
clock_t start, finish,s1,s2;
double duration;
srand(time(NULL)); // 시간값을 시드로 난수테이블 생성.
for(x=0;x<INPUT_SIZE;x++)
input[x] = rand();
for(x=0;x<INPUT_SIZE;x++)
input_sort[x] = x+1;
start=clock();
quick_sort(input,left,right);
finish=clock();
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("quick_sort = %f초 걸렸음.",duration);
s1 = clock();
qsort((void *)input,INPUT_SIZE,sizeof(int),sorting);
s2 = clock();
duration = (double)(s2-s1)/CLOCKS_PER_SEC;
printf("\nqsort = %f초 걸렸음.",duration);
s1 = clock();
qsort((void *)input_sort,INPUT_SIZE,sizeof(int),sorting);
s2 = clock();
duration = (double)(s2-s1)/CLOCKS_PER_SEC;
printf("\nSorted qsort = %f초 걸렸음.",duration);
start=clock();
quick_sort(input_sort,left,right);
finish=clock();
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("\nSorted quick_sort = %f초 걸렸음.",duration);
} int left = 0, right = INPUT_SIZE-1;
clock_t start, finish,s1,s2;
double duration;
srand(time(NULL)); // 시간값을 시드로 난수테이블 생성.
for(x=0;x<INPUT_SIZE;x++)
input[x] = rand();
for(x=0;x<INPUT_SIZE;x++)
input_sort[x] = x+1;
start=clock();
quick_sort(input,left,right);
finish=clock();
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("quick_sort = %f초 걸렸음.",duration);
s1 = clock();
qsort((void *)input,INPUT_SIZE,sizeof(int),sorting);
s2 = clock();
duration = (double)(s2-s1)/CLOCKS_PER_SEC;
printf("\nqsort = %f초 걸렸음.",duration);
s1 = clock();
qsort((void *)input_sort,INPUT_SIZE,sizeof(int),sorting);
s2 = clock();
duration = (double)(s2-s1)/CLOCKS_PER_SEC;
printf("\nSorted qsort = %f초 걸렸음.",duration);
start=clock();
quick_sort(input_sort,left,right);
finish=clock();
duration = (double)(finish-start)/CLOCKS_PER_SEC;
printf("\nSorted quick_sort = %f초 걸렸음.",duration);
void quick_sort(int input[], int left, int right)
{
int pivot,i,j,tmp;
if(left < right)
{
i=left;
j=right+1;
pivot = input[left];
do{
SWAP(input[left],input[j],tmp);
quick_sort(input,left,j-1);
quick_sort(input,j+1,right);
} j=right+1;
pivot = input[left];
do{
do{
do{
if(i<j) SWAP(input[i],input[j],tmp);
}while(i<j); i++;
}while(input[i] < pivot); do{
j--;
}while(input[j] > pivot); if(i<j) SWAP(input[i],input[j],tmp);
SWAP(input[left],input[j],tmp);
quick_sort(input,left,j-1);
quick_sort(input,j+1,right);
stdlib 에서 제공해주는 qsort() 함수와 교수님이 쓰시던 함수를 비교해서 속도를 재봤더니 신기하게도 교수님이 쓰시던게 더 빠르다고 나왔다. 모 책에서 보기론 qsort가 더럽게 빠르다고 해서 내심 기대하고 있었는데 거의 2배정도 차이난다. 하지만 문제는 재귀판인 교수님 소스는 데이터가 80만개가 넘어가면 행복한 에러를 내시고 사망.
하지만 qsort는 죽지않았다.
비재귀판인걸까? 그런데 속도는 더 느리다. 일반적으로 그게 가능한가?
그럴수도 있다고 생각되긴 하는데 교수님 말로는 재귀가 비재귀판보다 더 느리다고 하신다.
피보나치 수열 해결 알고리즘의 경우엔 이해가 가는데... 흠;;
# by | 2007/10/04 20:49 | STUDY | 트랙백 | 덧글(3)
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]