'C++프로그래밍/C'에 해당되는 글 1건

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 60000
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int n;

void bubble_sort(int list[],int n)
{
 int i,j,temp;
 for(i=n-1;i>0;i--){
  for(j=0;j<i;j++)
   if(list[j]>list[j+1])
   SWAP(list[j],list[j+1],temp);
 }
}
void main()
{
 int i;
 clock_t start , end;
 n=MAX_SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 bubble_sort(list,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//insertion_sort

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

#define MAX_SIZE 60000
//#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int n;

void insertion_sort(int list[],int n)
{
 int i,j,key;
 for(i=1;i<n;i++){
  key=list[i];
  for(j=i-1;j>=0 && list[j]>key;j--)
   list[j+1]=list[j];
  list[j+1]=key;
 }
}

void main()
{int i;
 clock_t start , end;
 n=MAX_SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 insertion_sort(list,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//merge_sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 60000

int sorted[MAX_SIZE];
int list[MAX_SIZE];
int n;

void merge(int list[],int left,int mid,int right)
{
 int i,j,k,l;
 i=left, j=mid+1; k=left;

 while(i<=mid && j<=right){
  if(list[i]<=list[j])
   sorted[k++]=list[i++];
  else
   sorted[k++]=list[j++];
 }
 if(i>mid)
  for(l=j;l<=right;l++)
   sorted[k++]=list[l];
 else
  for(l=i;l<=mid;l++);

 for(l=left;l<=right;l++)
  list[l]=sorted[l];
}

void merge_sort(int list[],int left,int right)
{
 int mid;
 if(left<right){
  mid=(left+right)/2;
  merge_sort(list,left,mid);
  merge_sort(list,mid+1,right);
  merge(list,left,mid,right);
 }
}

void main()
{
 int i;
 clock_t start , end;
 n=MAX_SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 merge_sort(list,0,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//quick_sort

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

#define MAX_SIZE 60000
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int partition(int left,int right)
{
 int pivot,temp;
 int low,high;
 
 low=left;
 high=right+1;
 pivot=list[left];
 do{
  do
  low++;
  while(low <= right && list[low]<pivot);
  do
  high--;
  while(high >= left && list[high]>pivot);
  if(low<high) SWAP(list[low],list[high],temp);
 }while(low<high);

 SWAP(list[left],list[high],temp);
 return high;
}
void quick_sort(int left,int right)
{
 int q;
 if(left<right){
  q=partition(left,right);
  quick_sort(left,q-1);
  quick_sort(q+1,right);
 }
}

int main()
{
 int i , n;
 clock_t start , end;
 n = MAX_SIZE;
 srand((unsigned)time(NULL));
 for(i = 0 ; i < n ; i++)
  list[i] = rand() % n;
 start = clock();
 quick_sort(0 , n-1);
 end = clock();
 printf("%lfsec \n",(end - start) / (double)1000);
}

//select_sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 60000
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

int list[MAX_SIZE];
int n;

void selection_sort(int list[],int n)
{
 int i,j,least,temp;
 for(i=0;i<n-1;i++){
  least=i;
  for(j=i+1;j<n;j++)
   if(list[j]<list[least]) least=j;
  SWAP(list[i],list[least],temp);
 }
}
void main()
{
int i;
 clock_t start , end;
 n=MAX_SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 selection_sort(list,n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}

//shell_sort

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

#define SIZE 60000

int a[SIZE];

void ShellSort(int n)
{
    int i,j,h,v;
    for(h=1 ; h<n ; h = 3*h+1) ;
    for( ; h > 0 ; h /=3)                     
        for ( i = h+1 ; i<=n ;i++)                                        
        {
            v = a[i];                                      
            j = i;                           
   while (j > h && a[j-h] > v)       
            {
                a[j] = a[j-h];                                                                 
                j = j - h;                                                                
            }a[j] = v;
  }
}

 void main()
{
    int i , n;
    double start_time;
 n = SIZE;

    srand((unsigned)time(NULL));

    for(i = 0; i< n; i++) a[i] = rand() % n;

    start_time = clock();
    ShellSort(n);

 printf("%lfsec\n", (clock()-start_time)/(double)1000);
 }

//heap_sort

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

#define SIZE 60000
int a[SIZE];

typedef struct HeapType {
 int heap[SIZE+1];
 int heap_size;
}HeapType;

void init(HeapType *h)
{
 h->heap_size=0;
}

void insert_max_heap(HeapType *h,int item)
{
 int i;
 i= ++(h->heap_size);

 while((i!=1)&&(item > h->heap[i/2])){
  h->heap[i]=h->heap[i/2];
  i/=2;
 }
 h->heap[i]=item;
}

int delete_max_heap(HeapType *h)
{
 int parent, child;
 int item, temp;

 item=h->heap[1];
 temp=h->heap[(h->heap_size)--];
 parent=1;
 child=2;
 while(child<=h->heap_size){
  if((child<h->heap_size)&&
   (h->heap[child] < h->heap[child+1]))
   child++;
  if(temp >=h->heap[child]) break;
  h->heap[parent]=h->heap[child];
  parent=child;
  child*=2;
 }
 h->heap[parent]=temp;
 return item;
}
void heap_sort(int n)
{
 int i;
 HeapType h;

 init(&h);
 for(i=0;i<n;i++){
  insert_max_heap(&h,a[i]);
 }
 for(i=(n-1);i>=0;i--){
  a[i]=delete_max_heap(&h);
 }
}

void main()
{
 int i , n;
 HeapType h;
 clock_t start , end;
 n = SIZE;

 for(i = 1 ; i <= n ; i++)
  a[i] = rand() % n;
    init(&h);
 start = clock();
 heap_sort(n);
 end = clock();
 printf("%lfsec \n",(end - start)/(double)1000);
 
}

//radix_sort

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

#define BUCKETS 10
#define DIGITS 5
#define MAX_QUEUE_SIZE 20000
#define SIZE 60000

typedef int element;
typedef struct{
 element queue[MAX_QUEUE_SIZE];
 int front,rear;
}QueueType;

int list[SIZE];

void error(char* message)
{
 fprintf(stderr,"%s\n",message);
 exit(1);
}

void init(QueueType* q)
{
 q->front=q->rear=0;
}

int is_empty(QueueType* q)
{
 return (q->front == q->rear);
}

int is_Full(QueueType* q)
{
 return ((q->rear+1)%MAX_QUEUE_SIZE ==q->front);
}
void enqueue(QueueType* q,element item)
{
 if(is_Full(q))
  error("큐가 포화상태입니다");
 q->rear=(q->rear+1)%MAX_QUEUE_SIZE;
 q->queue[q->rear]=item;
}

element dequeue(QueueType* q)
{
 if(is_empty(q))
  error("큐가 공백상태입니다");
 q->front=(q->front+1)%MAX_QUEUE_SIZE;
 return q->queue[q->front];
}

void radix_sort(int n)
{
 int i,b,d,factor=1;
 QueueType queues[BUCKETS];

 for(b=0;b<BUCKETS;b++) init(&queues[b]);

 for(d=0;d<DIGITS;d++){
  for(i=0;i<n;i++)
   enqueue(&queues[(list[i]/factor)%10],list[i]);

  for(b=i=0;b<BUCKETS;b++)
   while(!is_empty(&queues[b]))
    list[i++]=dequeue(&queues[b]);
  factor *=10;
 }
}

void main()
{
 int i,n;
 clock_t start , end;
 n=SIZE;
 for(i=0;i<n;i++)
  list[i]=rand()%n;

 start = clock();
 radix_sort(n);
 end = clock();
  printf("%lfsec\n",(end - start)/(double)1000);
}