삽입 정렬(Insertion-Sort)

삽입 정렬(Insertion Sort)

- 배열의 모든 원소를 앞에서 부터 차례대로 비교하여, 자신의 위치를 찾아 삽입하는 방식

- 작은 원소의 정렬에 효율적인 알고리즘

- *In-place 알고리즘의 한 종류

  * 원소를 저장하고 있는 초기 배열의 아주 작은 추가적인 공간만 요구하는 알고리즘

  * "아주 작은"이란 n 개의 원소를 정렬할 때, O(log n) 만큼의 추가 공간이 요구되는 것

 

 

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

#define MAX  10 // size of array

void display_elements( int *, int);
void insertion_sort( int *, int);

int main( void)
{
 int arry[MAX]  = { 0,};
 int count   = 0;
 int size   = 0;

 srand( time(NULL)); // used to init random

 size  = sizeof(arry)/4;

 // init elements of array with random numbers
 for( count = 0 ; count < size ; count ++)
 {
  arry[count]  = rand()%(MAX*10);
 }

 // display elements of array
 printf("Before sorting : ");
 display_elements( arry, size);

 // call Insertion-Sort
 insertion_sort( arry, size);

 // output result
 printf("\n After sorting : ");
 display_elements( arry, size);

 return 0;
}

void display_elements( int *ar, int s)
{
 int count  = 0;

 for( count = 0 ; count < s ; count ++)
 {
  printf("%4d", ar[count]);
 }
}

void insertion_sort( int *ar, int s)
{
 int key  = 0;
 int i, j;

 for( i = 1 ; i < s ; i ++)
 {
   key = ar[i]; // back up original value

   j = i; // set starting position

   // push elements back
   while( ( --j >= 0) && ( key < ar[j]))
   {
    ar[j+1] = ar[j];
   }

   ar[j+1]  = key;
 }
}