정렬 알고리즘

정렬(Sort) : 임의의 순서대로 배열되어 있는 자료를 자료의 집합을 일정한 순서대로 재배열하는 것.

 

정렬은 컴퓨터로 문제 해결을 하는데 있어서 검색과 함께 가장 많이 부닥치는 문제이다. 일반적으로 가장 빠른 정렬 알고리즘은 퀵 정렬(Quick Sort)이라고 알려져 있고 실제로도 가장 빠른 속력을 나타낸다. 하지만 퀵 정렬은 거의 정렬이 되어 있는 자료에 대해서는 다른 기본적인 정렬 알고리즘보다는 성능이 떨어진다. 이렇게 어떤 알고리즘이 가장 좋은 알고리즘이라는 일반해는 없다. 단지 주어진 사황과 여건에 가장 적합한 알고리즘이 있을 뿐이다.

데이터를 정렬하는 이유는 검색을 빠르게 하기 위함입니다.

정렬을 하는 방법에 따라 두 종류로 나눌 수 있습니다. 하나는 내부정렬(Internal Sorting)이고, 나머지는 외부정렬(External Sorting)입니다.

내부정렬은 데이터의 크기가 주기억장소 용량보다 적을 경우 기억장소를 활용하여 정렬하는 방법을 말하며 외부정렬은 데이터의 크기가 주기억장소 용량보다 큰 경우 외부 기억 장치를 사용하여 정렬하는 방법을 말합니다. 보통 정렬 알고리즘을 말할 때는 내부정렬 알고리즘을 말합니다.

 

정렬 알고리즘의 종류

단순한 알고리즘 : 선택정렬, 삽입정렬, 거품정렬, 셀 정렬(안정되어 있고 구현이 쉬움)

복잡한 알고르즘 : 퀵 정렬, 기수정렬, 힙 정렬, 병합 정렬(정렬 속도가 빠름)

 

Source code

선언부 

* programmed by  Kim eung oh  */

/*  정렬(sorting)프로그램   */

 

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

#include <time.h>

 

#define MAX 100

 

초기화 함수 

void init_arr(int arr[], int n) // 배열의 초기화 함수 
{
 int i;
 srand((int)time(NULL));

 for(i=0; i<n; i++)
 {
  arr[i]=rand()%100;
 }
}

  

화면에 출력해주는 함수 

void show(int arr[], int n) // 화면에 출력 해주는 함수
{
 int i;

 for(i=0; i<n; i++)
 {
  printf(" %4d", arr[i]);
 }
 printf("\n");
}

 

메뉴 함수

int menu() // 사용자로부터 원하는 정렬을 입력받는 함수
{
 int input;

 puts("\n 원하는 정렬 방식을 결정하세요 ?(종료시 : 0) ");
 puts(" 1번) 선택정렬 \n 2번) 삽입정렬 \n 3번) 버블정렬 \n 4번) 쉘정렬 \n 5번) 퀵정렬");
 fputs(" 입력 ", stdout), scanf("%d", &input);
 return input;
}

 

선택정렬(Selection Sort)

최소값을 앞으로 보내는 정렬- 안정성이 좀 떨어짐

void select_sort(int arr[], int n)  // 선택정렬함수
{
 int min;
 int minindex;
 int i,j;

 for(i=0; i<n-1; i++)
 {
  minindex=i;  // 최소값 저장
  min=arr[i];
  for(j=i+1; j<n; j++)
  {
   if(min>arr[j])
   {
    min=arr[j];
    minindex=j;
   }
  }
  arr[minindex]=arr[i]; // 최소값이 있던 배열에 최초 배열의 값 저장
  arr[i]=min;  // 최소 인텍스에 최소값 저장
 }

}

  

삽입정렬(Insertion Sort)

값을 비교를 통해서 앞으로 최소값을 보내는 정렬

void insert_sort(int arr[], int n)  // 삽입정렬함수
{
 int i,j,t;
 for(i=1; i<n; i++)
 {
  t=arr[i];
  j=i;
  while(arr[j-1] > t && j>0)
  {
   arr[j]=arr[j-1];
   j--;
  }
  arr[j]=t;
 }
}

 

간접정렬(indirevt_insert_sort())

void indirect_sort(int a[], int index[], int n)
{
 int i, j;
 int t;

 for(i=0; i<n; i++) // 인덱스 배열의 초기화
 {
  index[i]=i;
 }

 for(i=1; i<n; i++) // 삽입정렬
 {
  t=index[i];
  j=i;
  while(a[index[j-1]]>a[t] && j>0) // 삽입될 곳을 찾음
  {
   index[j]=index[j-1]; // 인덱스의 배열을 조정
   j--;
  }
  index[j]=t; // 삽입함
 }
}

 

거품정렬(Bubble Sort)

배열의 인접 요소(adjacent element)를 비교하여 교환

void bubble_sort(int a[], int n) // 버블 정렬함수
{
 int i, j, t;
 for(i=0; i<n-1; i++)
 {
  for(j=1; j<n-i; j++)
  {
   if(a[j-1]>a[j])  // 인접요소의 비교
   {
    t=a[j-1];
    a[j-1]=a[j];
    a[j]=t;
   }
  }
 }
}

 

쉘 정렬(Shell Sort)

삽입정렬의 단점을 보완하여 어느정도 거리가 떨어진 요소를 비교하여 교환하는 방식 

void shell_sort(int a[], int n) //셀정렬 함수
{
 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=a[j];
    k=j;
    while(k>h-1 && a[k-h]>v)
    {
     a[k]=a[k-h];
     k-=h;
    }
    a[k]=v;
   }
  }
 }
}

 

퀵 정렬(Quick Sort)

연속적인 분할(Partition)에 의해서 정렬

void quick_sort(int a[], int n) // 퀵정렬 함수
{
 int v, t;
 int i, j;
 
 if(n>1)
 {
  v=a[n-1];
  i=-1;
  j=n-1;
  while(1)
  {
   while(a[++i]<v);
   while(a[--j]>v);
   if(i>=j) break;
   t=a[i];
   a[i]=a[j];
   a[j]=t;
  }
  t=a[i];
  a[i]=a[n-1];
  a[n-1]=t;
  quick_sort(a,i);
  quick_sort(a+i+1, n-i-1);
 }
}

 

메인함수 

int main()
{
 int arr[MAX];
// int index[MAX]; // 간접정렬함수의 인덱스 배열
 int length=sizeof(arr)/sizeof(int);
 int result=1;
 
 while((result=menu())!=0)
 {
  if(result>5 || result<0)
   break;
  init_arr(arr, length);
 
  puts("\n ** 초기화된 배열 **");
  show(arr, length);

  if(result==1)
   select_sort(arr, length);
  else if(result==2)
   insert_sort(arr, length);
  else if(result==3)
   bubble_sort(arr, length);
  else if(result==4)
   shell_sort(arr, length);
  else if(result==5)
   quick_sort(arr, length);
  else
   break;
  puts(" ** 정렬 후 배열 **");
  show(arr, length);
 }
 
 // indirect_sort(arr, index, length);  // 간접정렬 함수 출력
 // show(index, length);
 
 return 0;
}