2007년 10월 08일

여러가지 정렬방법 - 시간복잡도 계산.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define INPUT_SIZE 80000 // element
#define SWAP(x,y,t) ((t=x),(x=y),(y=t))
#define HEAP_EMPTY(n) (!n) // is empty?

void quick_sort(int [],int,int);
void insertion_sort(int [],int);
void shell_sort(int [],int);
void insert_max_heap(int, int*, int [],int);
int delete_max_heap(int*, int []);
int sorting(const void*, const void*);

static int list1[INPUT_SIZE/8]; // 10000
static int list2[INPUT_SIZE/4]; // 20000
static int list3[INPUT_SIZE/2]; // 40000
static int list4[INPUT_SIZE]; // 80000

static int heap1[INPUT_SIZE/4];
static int heap2[INPUT_SIZE/2];
static int heap3[INPUT_SIZE];
static int heap4[(INPUT_SIZE)*2];
static int idx = 0; // init , number of data

int main(void)
{
int cnt,elem; // counter
srand(time(NULL)); // time seed for srand
clock_t start,end; // clock declare
////////////////////////////// QUICK_SORT /////////////////////////////////
/****************************** random ***********************************/    

int left = 0, right = (INPUT_SIZE/8)-1;
printf("●●● 임의의 수로 채워진 데이터 \n\n");
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = rand();  // make random num

start = clock();
quick_sort(list1,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);

left = 0, right = (INPUT_SIZE/4)-1;
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = rand();  // make random num
start = clock();
quick_sort(list2,left,right);
end = clock();
printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);

left = 0, right = (INPUT_SIZE/2)-1;

for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = rand();  // make random num

start = clock();
quick_sort(list3,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);

left = 0, right = (INPUT_SIZE)-1;

for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = rand();  // make random num

start = clock();
quick_sort(list4,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);
/***************************************************************************/    
/******************************* ascent ************************************/
left = 0, right = (INPUT_SIZE/8)-1;
printf("\n●●● 오름차순으로 정렬된 데이터\n\n");
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = cnt+1;  // make random num

start = clock();
quick_sort(list1,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);

left = 0, right = (INPUT_SIZE/4)-1;

for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = cnt+1;  // make random num

start = clock();
quick_sort(list2,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    

left = 0, right = (INPUT_SIZE/2)-1;

for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = cnt+1;  // make random num

start = clock();
quick_sort(list3,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
left = 0, right = (INPUT_SIZE)-1;

for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = cnt+1;  // make random num

start = clock();
quick_sort(list4,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    
/***************************************************************************/    
/****************************** descent ************************************/
left = 0, right = (INPUT_SIZE/8)-1;
printf("\n●●● 내림차순으로 정렬된 데이터\n\n");
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = INPUT_SIZE/8 - cnt;  // make random num

start = clock();
quick_sort(list1,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);

left = 0, right = (INPUT_SIZE/4)-1;

for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = INPUT_SIZE/4 - cnt;  // make random num

start = clock();
quick_sort(list2,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    

left = 0, right = (INPUT_SIZE/2)-1;

for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = INPUT_SIZE/2 - cnt;  // make random num

start = clock();
quick_sort(list3,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
left = 0, right = (INPUT_SIZE)-1;

for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = INPUT_SIZE - cnt;  // make random num

start = clock();
quick_sort(list4,left,right);
end = clock();

printf("●●● [%d]개의 데이터 : quick_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);        
/***************************************************************************/    
////////////////////////////// QUICK_SORT ///////////////////////////////////

///////////////////////////////// QSORT /////////////////////////////////////
/******************************* random ************************************/

printf("\n●●● 임의의 수로 채워진 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = rand();  // make random num

start = clock();
qsort((void*)list1,INPUT_SIZE/8,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = rand();  // make random num

start = clock();
qsort((void*)list2,INPUT_SIZE/4,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = rand();  // make random num

start = clock();
qsort((void*)list3,INPUT_SIZE/2,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = rand();  // make random num

start = clock();
qsort((void*)list4,INPUT_SIZE,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);
/***************************************************************************/    
/******************************* ascent ************************************/
printf("\n●●● 오름차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = cnt+1;  // make random num

start = clock();
qsort((void*)list1,INPUT_SIZE/8,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = cnt+1;  // make random num

start = clock();
qsort((void*)list2,INPUT_SIZE/4,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = cnt+1;  // make random num

start = clock();
qsort((void*)list3,INPUT_SIZE/2,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = cnt+1;  // make random num

start = clock();
qsort((void*)list4,INPUT_SIZE,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    

/***************************************************************************/    
/****************************** descent ************************************/

printf("\n●●● 내림차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = INPUT_SIZE/8 - cnt;  // make random num

start = clock();
qsort((void*)list1,INPUT_SIZE/8,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = INPUT_SIZE/4 - cnt;  // make random num

start = clock();
qsort((void*)list2,INPUT_SIZE/4,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = INPUT_SIZE/2 - cnt;  // make random num

start = clock();
qsort((void*)list3,INPUT_SIZE/2,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = INPUT_SIZE - cnt;  // make random num

start = clock();
qsort((void*)list4,INPUT_SIZE,sizeof(int),sorting);
end = clock();

printf("●●● [%d]개의 데이터 : qsort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    

/***************************************************************************/    
////////////////////////////////// QSORT ////////////////////////////////////

////////////////////////////// INSERTION_SORT ///////////////////////////////
/******************************* random ************************************/
printf("\n●●● 임의의 수로 채워진 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = rand();  // make random num

start = clock();
insertion_sort(list1,INPUT_SIZE/8);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = rand();  // make random num

start = clock();
insertion_sort(list2,INPUT_SIZE/4);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = rand();  // make random num

start = clock();
insertion_sort(list3,INPUT_SIZE/2);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = rand();  // make random num

start = clock();
insertion_sort(list4,INPUT_SIZE);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/1,(double)(end-start)/CLOCKS_PER_SEC);
/***************************************************************************/
/******************************* ascent ************************************/
printf("\n●●● 오름차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = cnt+1;  // make random num

start = clock();
insertion_sort(list1,INPUT_SIZE/8);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = cnt+1;  // make random num

start = clock();
insertion_sort(list2,INPUT_SIZE/4);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = cnt+1;  // make random num

start = clock();
insertion_sort(list3,INPUT_SIZE/2);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = cnt+1;  // make random num

start = clock();
insertion_sort(list4,INPUT_SIZE);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/1,(double)(end-start)/CLOCKS_PER_SEC);    
/***************************************************************************/    
/****************************** descent ************************************/
printf("\n●●● 내림차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = INPUT_SIZE/8 - cnt;  // make random num

start = clock();
insertion_sort(list1,INPUT_SIZE/8);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = INPUT_SIZE/4 - cnt;  // make random num

start = clock();
insertion_sort(list2,INPUT_SIZE/4);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = INPUT_SIZE/2 - cnt;  // make random num

start = clock();
insertion_sort(list3,INPUT_SIZE/2);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);    
for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = INPUT_SIZE - cnt;  // make random num

start = clock();
insertion_sort(list4,INPUT_SIZE);
end = clock();

printf("●●● [%d]개의 데이터 : insertion_sort = %f 초 걸렸음 \n",
INPUT_SIZE/1,(double)(end-start)/CLOCKS_PER_SEC);


/******************************************************************************/    
/////////////////////////////// INSERTION_SORT /////////////////////////////////

///////////////////////////////// SHELL_SORT ///////////////////////////////////
/********************************* random *************************************/    
printf("\n●●● 임의의 수로 채워진 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = rand();  // make random num

start = clock();
shell_sort(list1,INPUT_SIZE/8);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = rand();  // make random num

start = clock();
shell_sort(list2,INPUT_SIZE/4);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = rand();  // make random num

start = clock();
shell_sort(list3,INPUT_SIZE/2);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = rand();  // make random num

start = clock();
shell_sort(list4,INPUT_SIZE);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);
/***************************************************************************/
/******************************* ascent ************************************/
printf("\n●●● 오름차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = cnt+1;  // make random num

start = clock();
shell_sort(list1,INPUT_SIZE/8);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = cnt+1;  // make random num

start = clock();
shell_sort(list2,INPUT_SIZE/4);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = cnt+1;  // make random num

start = clock();
shell_sort(list3,INPUT_SIZE/2);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = cnt+1;  // make random num

start = clock();
shell_sort(list4,INPUT_SIZE);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    
/***************************************************************************/    
/****************************** descent ************************************/
printf("\n●●● 내림차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = INPUT_SIZE/8 - cnt;  // make random num

start = clock();
shell_sort(list1,INPUT_SIZE/8);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = INPUT_SIZE/4 - cnt;  // make random num

start = clock();
shell_sort(list2,INPUT_SIZE/4);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = INPUT_SIZE/2 - cnt;  // make random num

start = clock();
shell_sort(list3,INPUT_SIZE/2);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);

for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = INPUT_SIZE - cnt;  // make random num

start = clock();
shell_sort(list4,INPUT_SIZE);
end = clock();

printf("●●● [%d]개의 데이터 : shell_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    
/****************************************************************************/    
//////////////////////////////// SHELL_SORT //////////////////////////////////

///////////////////////////////// HEAP_SORT //////////////////////////////////
/******************************** random *************************************/
printf("\n●●● 임의의 수로 채워진 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = rand();  // make random num
idx = 0;
elem = INPUT_SIZE/4;    
start = clock();    
for(cnt = 0; cnt<INPUT_SIZE/8 ; cnt++)
insert_max_heap(list1[cnt],&idx,heap1,elem);
for(cnt = 0; cnt<INPUT_SIZE/8 ; cnt++)
delete_max_heap(&idx,heap1);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = rand();  // make random num

elem = INPUT_SIZE/2;    
idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE/4 ; cnt++)
insert_max_heap(list2[cnt],&idx,heap2,elem);
for(cnt = 0; cnt<INPUT_SIZE/4 ; cnt++)
delete_max_heap(&idx,heap2);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = rand();  // make random num

elem = INPUT_SIZE;

idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE/2 ; cnt++)
insert_max_heap(list3[cnt],&idx,heap3,elem);
for(cnt = 0; cnt<INPUT_SIZE/2 ; cnt++)
delete_max_heap(&idx,heap3);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = rand();  // make random num

elem = INPUT_SIZE*2;

idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE ; cnt++)
insert_max_heap(list4[cnt],&idx, heap4,elem);
for(cnt = 0; cnt<INPUT_SIZE ; cnt++)
delete_max_heap(&idx,heap4);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    
/***************************************************************************/
/******************************* ascent ************************************/
printf("\n●●● 오름차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = cnt+1;  // make random num
idx = 0;
elem = INPUT_SIZE/4;    
start = clock();    
for(cnt = 0; cnt<INPUT_SIZE/8 ; cnt++)
insert_max_heap(list1[cnt],&idx,heap1,elem);
for(cnt = 0; cnt<INPUT_SIZE/8 ; cnt++)
delete_max_heap(&idx,heap1);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = cnt+1;  // make random num

elem = INPUT_SIZE/2;    
idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE/4 ; cnt++)
insert_max_heap(list2[cnt],&idx,heap2,elem);
for(cnt = 0; cnt<INPUT_SIZE/4 ; cnt++)
delete_max_heap(&idx,heap2);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = cnt+1;  // make random num

elem = INPUT_SIZE;    
idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE/2 ; cnt++)
insert_max_heap(list3[cnt],&idx,heap3,elem);
for(cnt = 0; cnt<INPUT_SIZE/2 ; cnt++)
delete_max_heap(&idx,heap3);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = cnt+1;  // make random num

elem = INPUT_SIZE*2;    
idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE ; cnt++)
insert_max_heap(list4[cnt],&idx, heap4,elem);
for(cnt = 0; cnt<INPUT_SIZE ; cnt++)
delete_max_heap(&idx,heap4);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    
/***************************************************************************/    
/****************************** descent ************************************/
printf("\n●●● 내림차순으로 정렬된 데이터 \n\n");    
for(cnt = 0; cnt < INPUT_SIZE/8 ; cnt++)
list1[cnt] = INPUT_SIZE/8 - cnt;  // make random num
idx = 0;
elem = INPUT_SIZE/4;    
start = clock();    
for(cnt = 0; cnt<INPUT_SIZE/8 ; cnt++)
insert_max_heap(list1[cnt],&idx,heap1,elem);
for(cnt = 0; cnt<INPUT_SIZE/8 ; cnt++)
delete_max_heap(&idx,heap1);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/8,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE/4 ; cnt++)
list2[cnt] = INPUT_SIZE/4 - cnt;  // make random num

elem = INPUT_SIZE/2;    
idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE/4 ; cnt++)
insert_max_heap(list2[cnt],&idx,heap2,elem);
for(cnt = 0; cnt<INPUT_SIZE/4 ; cnt++)
delete_max_heap(&idx,heap2);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/4,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE/2 ; cnt++)
list3[cnt] = INPUT_SIZE/2 - cnt;  // make random num

elem = INPUT_SIZE;

idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE/2 ; cnt++)
insert_max_heap(list3[cnt],&idx,heap3,elem);
for(cnt = 0; cnt<INPUT_SIZE/2 ; cnt++)
delete_max_heap(&idx,heap3);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE/2,(double)(end-start)/CLOCKS_PER_SEC);        


for(cnt = 0; cnt < INPUT_SIZE ; cnt++)
list4[cnt] = INPUT_SIZE-cnt;  // make random num

elem = INPUT_SIZE*2;

idx = 0;
start = clock();
for(cnt = 0; cnt<INPUT_SIZE ; cnt++)
insert_max_heap(list4[cnt],&idx, heap4,elem);
for(cnt = 0; cnt<INPUT_SIZE ; cnt++)
delete_max_heap(&idx,heap4);
end = clock();

printf("●●● [%d]개의 데이터 : heap_sort = %f 초 걸렸음 \n",
INPUT_SIZE,(double)(end-start)/CLOCKS_PER_SEC);    
/***************************************************************************/    
//////////////////////////////// HEAP_SORT //////////////////////////////////

return 0;
}


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{
do{
i++;
}while(input[i] < pivot);
do{
j--;
}while(input[j] > pivot);

if(i<j) SWAP(input[i],input[j],tmp);
}while(i<j);
SWAP(input[left],input[j],tmp);
quick_sort(input,left,j-1);
quick_sort(input,j+1,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;
}
void insertion_sort(int list[],int n) // insertion sort
{
int i,j,t;
for(i = 1; i < n ; i++)
{
t = list[i];
j = i;
while(list[j-1] > t && j > 0) // search
{
list[j] = list[j-1];
j--;
}
list[j] = t;
}
}
void shell_sort(int list[], int n) // shell sort
{
int i, j, k, h, v;
for(h = n/2; h > 0 ; h /= 2)
{
for(i = 0 ; i < h ; i++)
{
for(j = i+h ; j < n ; j += h)
{
v = list[j];
k = j;
while( k > h-1 && list[k-h] > v)
{
list[k] =  list[k -h];
k -= h;
}
list[k] = v;
}
}
}
}



void insert_max_heap(int item, int *idx,int heap[],int elem) // heap insert
{
int i;

if(elem-1 == (*idx)){
fprintf(stderr,"heap is full\n");
exit(1);
}    

i = ++(*idx);

while((i!=1) && (item < heap[i/2])) {
heap[i] = heap[i/2];
i /= 2;
}
heap[i] = item;
}
int delete_max_heap(int *idx,int heap[]) // heap delete
{
int item, temp, parent, child;
if(HEAP_EMPTY(*idx))
{
printf("heap is empty!\n");
exit(-1);
}
item =  heap[1];
temp = heap[(*idx)--];
parent = 1;
child = 2;

while(child <= *idx)
{
if((child > *idx) && (heap[child] > heap[child + 1])) child ++;
if(temp <= heap[child]) break;

heap[parent] =  heap[child];
parent = child;
child *= 2;
}
heap[parent] =  temp;
return item;
}

// 일단 여기까지~ gg -_ㅠ
, , , , 

by muzie | 2007/10/08 03:38 | STUDY | 트랙백 | 덧글(0)

트랙백 주소 : http://muzie.egloos.com/tb/3425999
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶