C, 소트 구현 소스 bubble, selection, insertion, quick, merge, heap sort

/* sort.c */
/* 1998.12.7. LEE SANG HWAN */
/* 도움말 추가 by Oh SangMoon */

 

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAXLENGTH 1024

 

int parser( char *p, char *argv[], int maxargc )
{
 int argc = 0;

 while ( *p )
 {
  while ( *p && isspace( *p ) ) p++;

  if ( ! *p ) return( argc );
  argv[argc++] = p++;

  while ( *p && !isspace( *p ) ) p++;
  if( *p ) *p++ = 0;

  if ( argc >= maxargc ) return( argc );
 }
 return ( argc );
}

 

extern int show(int *list, int num);

 

void bubble_sort(int *list, int num)
{
 int temp;
 int i, j;

 for(i = num; i > 1; i--) /* 비교를 수행할 원소의 갯수 */
 {
  for(j = 1; j < i; j++)
   if(list[j] > list[j + 1])
   { 
    temp = list[j + 1];
    list[j + 1] = list[j];
    list[j] = temp;
   }
  show(list, num);
 }
}

 

void selection_sort(int *list, int num)
{
 int temp;
 int i, j;
 int maxidx;

 for(i = num; i > 1; i--) /* 비교를 수행할 원소의 갯수 */
 {
  maxidx = 1;
  for(j = 1; j < i; j++)
   if(list[maxidx] < list[j + 1])
   {
    maxidx = j + 1; /* 현재까지 가장 큰 값의 인덱스 저장 */
   }

  /* i 값을 처음부터 i번째 원소까지 비교해서 최대값을 찾아낸 후
   저장하는 장소를 의미한다. */
  temp = list[i];
  list[i] = list[maxidx];
  list[maxidx] = temp;
  show(list, num);
 }
}

                                                                
void insert_one_item(int r, int *list, int i)
{
 int j = i;
 while(r < list[j])
 {
  list[j + 1] = list[j];
  j = j - 1;
 }
 list[j + 1] = r;
}

 

void insertion_sort(int *list, int num)
{
 int i;

 for(i = 2; i <= num; i++)
 {
  insert_one_item(list[i], list, i - 1);
  show(list, num);
 }
}

 

void interchange(int *list, int i, int j)
{
 int temp;
 temp = list[i];
 list[i] = list[j];
 list[j] = temp;
}

 

void quick_sort(int *list, int m, int n)
{
 int i, j, k;

 if(m >= n)
  return ;
 k = list[m];
 i = m ;
 j = n + 1;
 while(i < j)
 {
  do {
   i++;
  } while((k > list[i]) && (i < n));
  do {
   j--;
  } while(k < list[j]);
  if(i < j)
   interchange(list, i, j);
 }
 interchange(list, m, j);
 show(list, 9);
 quick_sort(list, m, j - 1);
 quick_sort(list, j + 1, n);
}

void twoway_merge(int *x, int *z, int l, int m, int n)
{
 int i, j, k, t;

 i = l;           /* 첫 번째 리스트의 시작 인덱스 */
 j = m + 1;        /* 두 번째 리스트의 시작 인덱스 */
 k = l;           /* 합병 결과를 저장할 리스트의 시작 인덱스, 이 인덱스는
            주어진 내용이 l 부터 n 까지를 합병하는 것이기 때문에
                    새로운 리스트에서도 l 부터 합병해야 한다. */
 while ((i <= m ) && ( j <= n))   /* 두 리스트 중 하나가 끝날 때까지 반복 */
 {
  if (x[i] <= x[j]) /* 첫 번째 리스트가 작은 경우 */
  {
   z[k] = x[i];  
   i = i + 1; /* 인덱스 이동 */
  }
  else /* 두 번째 리스트가 작은 경우 */
  {
   z[k] = x[j]; 
   j = j + 1; /* 인덱스 이동 */
  }
  k = k + 1;
 }
 if (i > m) /* 첫 번째 리스트는 다 사용했음을 의미함 */
  for (t = j; t <= n; t++)    
   z[k + t - j] = x[t]; /* 두 번째 리스트를 복사 */
 else
  for (t = i; t <= m; t++)
   z[k + t - i] = x[t]; /* 두 번째 리스트를 복사 */
}

 

void merge_pass (int *x, int *y, int n, int len)
{
 int i, j;
 i = 1;
 while (i <= (n - 2 * len + 1))
  /*  윗 줄에서 n - 2 * len+ 1은 길이가 len인 두 개의 리스트가
  존재할 때 까지를 의미한다. 만약 i 가 n - 2 * len+ 1 보다 크게 되면
  처리하고 남아 있는 부분이 길이가 length인 두 개의 리스트를
  형성하지 못한다. 이럴 경우는 다른 방식으로 처리해야하기 때문에
  while 루프의 조건문이 이렇게 형성되어 있다.*/
 {
  /* i + len- 1은 첫번째 리스트의 마지막 인덱스이고,
  i + 2 * len- 1은 두번째 리스트의 마지막 인덱스이다. */
  twoway_merge (x, y, i, i + len- 1, i + 2 * len- 1);
  i = i + 2 * len; /* i 는 len의 2 배만큼씩 증가시킨다. */
 }
 if ((i + len- 1) < n)
  /* 남은 두 리스트를 합병하는데 두 번째 리스트의 마지막 인덱스는
  n 이 된다. 따라서 두 번째 리스트는 길이가 len보다 작게 된다. */
  twoway_merge (x, y, i, i + len - 1, n);    
 else
 { /* 길이가 len보다 작은 리스트가 없는 경우는 그냥 복사한다 */
  for (j = i; j <= n; j++)               
   y[j] = x[j];
 }
 show(y, 9);
}

 

void merge_sort(int *list, int n)
{
 int len;
 int temp[MAXLENGTH]; /* 중간에 저장을 위해 사용하는 기억 장소 */

 len = 1;          /* 처음 합병할 리스트들의 길이는 1이다. */
 while (len < n)   /* 합병된 리스트의 길이가 n이 될 때까지 반복 */
 {
  merge_pass(list, temp, n, len);    /* x에 저장된 리스트를 y에 합병 */
   /* 이 과정이 끝나고 나면 리스트 전체가 y 에 들어가 있기 때문에 이를
   다시 x로 옮겨야 한다. 이 때 그냥 복사하는 것이 아니고
   merge_pass를 통해서 한 단계 더 정렬을 시도한다.*/
  len = 2 * len; /* 한 번의 merge_pass 후에는 합병할 리스트의 길이가 2 배가 된다. */
  merge_pass(temp, list, n, len);    /* y에 저장된 리스트를 x에 합병 */
  len = 2 * len;
  /* 다시 x에 저장이 된다. */
    }
}

 

void adjust(int *list, int i, int n)
/* i : adjust 알고리즘을 시작하는 노드의 인덱스 */
/* n : 전체 노드의 개수 */
{
 int j, k, done;

 done = 0; /* 아직 끝나지 않았음을 표시 */
 k = list[i]; /* 뿌리 노드이 값, 즉 옮겨야 할 원소의 값 */
 j = 2 * i; /* i 노드의 좌 자 노드 */
 while ((j <= n) && (!done))     /* 자식노드가 있고 not done일 때까지 반복 */
 {
  if ( j < n)  /* j + 1 <= n 과 마찬가지인데 우 자 노드의 존재를 검사 */
   if (list[j] < list[j + 1])      
    j = j + 1;  /* 자 노드들 중 큰 노드를 선택 */
  if (k >= list[j])
   done = 1;  /* 자 노드보다 크므로 수행을 중단 */
  else{
   list[j / 2] = list[j];  /* 자 노드를 부노드로 끌어 올림, 자 노드에 k 값을 쓰지 않는
                           이유는 나중에 수행이 다 끝난 다음에 쓰기 때문임. */
   j = 2 * j;   }
 }
 list[j / 2] = k; /* 수행이 끝나면 찾아낸 위치에 맨 처음 저장한 뿌리 노드의 값을 저장 */
}

void heap_sort(int *list, int n)
{
 int i, temp;

 show(list, 9);
 for (i = (n / 2); i >= 1; i--)      /* 초기 히프 만들기 */
  adjust(list, i, n);
 show(list, 9);
 for (i = (n - 1); i >= 1; i--)      /* 히프 정렬의 두 번째 단계 */
 {
  temp = list[i + 1];     /* 마지막 노드와 뿌리 노드의 교환 */  
  list[i + 1] = list[1];
  list[1] = temp;
  show(list, 9);
  adjust(list, 1, i); /* i개의 키에 대하여 adjust 적용 */
  show(list, 9);
 }
}

 

int data(int *list, int argc, char *argv[])
{
 int i = 0;

 for(i = 1; i < argc; i++)
 {
  list[i] = atoi(argv[i]);
 }
 return i - 1;
}

 

int show(int *list, int num)
{
 char buf[2048];
 char *ptr = buf;
 int i;

 for(i = 1; i <= num; i++)
 {
  if(i % 10 == 0)
  {
   sprintf(ptr, "\n");
   ptr++;
  }
  sprintf(ptr, "%3d ", list[i]);
  ptr += 4;
 }

 printf("%s\n", buf);
 return 1;
}

 

void main()
{
 char buf[128];
 char *argv[100];
 int  argc;
 char *prompt = "\nSORT> ";
 int org[MAXLENGTH];
 int list[MAXLENGTH];
 int num = 0;

 org[0] = 0xffffffff;
 list[0] = 0xffffffff;

  printf("Command: bubble, selection, insertion, quick, merge, heap, help or quit\n");

 

 while(1)
 {
  printf(prompt);
  gets(buf);
  argc = parser( buf, argv, 100 );

  if(argc == 0)
   continue;
 
  org[1] = 4;
  org[2] = 3;
  org[3] = 8;
  org[4] = 5;
  org[5] = 1;
  org[6] = 9;
  org[7] = 2;
  org[8] = 7;
  org[9] = 6;
  num = 9;

  memcpy(list, org, sizeof(int) * (num + 1));

  if(!strcmp(argv[0], "data"))
  {
   num = data(org, argc, argv);
  }
  else if(!strcmp(argv[0], "show"))
  {
   show(list, num);
  }
  else if(!strcmp(argv[0], "bubble"))
  {
   bubble_sort(list, num);
  }
  else if(!strcmp(argv[0], "selection"))
  {
   selection_sort(list, num);
  }
  else if(!strcmp(argv[0], "insertion"))
  {
   insertion_sort(list, num);
  }
  else if(!strcmp(argv[0], "quick"))
  {
   quick_sort(list, 1, num);
  }
  else if(!strcmp(argv[0], "merge"))
  {
   merge_sort(list, num);
  }
  else if(!strcmp(argv[0], "heap"))
  {
   heap_sort(list, num);
  }
  else if(!strcmp(argv[0], "quit"))
  {
   printf("stop operation of the sorting algorithms \n");
   break;
  }
  
  else if(!strcmp(argv[0], "help"))
  {
      printf("Command: bubble, selection, insertion, quick, merge, heap, help or quit\n", argv[0]);

  }
  else
  {
   printf("Invalid Command : %s\n", argv[0]);
  }
 }
}

 

/* The End */