3.정렬 알고리즘(Sort algorithm) - 삽입 정렬(insertion sort)

 

3.  삽입 정렬(Insertion Sort)

가장 간단하고 쉬운 정렬 방식이라고 볼 수 있다.

 

배열을 처음부터 하나하나 비교하여 자신한테 맞는 자리를 찾아가는 정렬 방식이다.

(1번째 값을 기준으로 하기 때문에 배열의 2번째 값에서부터 정렬을 시작한다.)

 

삽입 정렬의 특징

• 구현이 간단하지만 배열의 길이 만큼 비교하기 때문에 배열이 길어질수록 효율이 떨어진다.
• Insertion Sort 는 stable 한 정렬이다.
• Insertion Sort 는 in-place 한 정렬이다.
• Insertion Sort 는 comparison 한 정렬이다.

#include <stdio.h>

void insertion_sort(int * array, int max_size)
{
  int size = max_size;
  int i, j, remember;

  printf("before : \n");
  for(i=0;i<size;i++)
  {
    printf("%2d ", array[i]);
  }
  printf("\n");

  for(i=1;i<size;i++)
  {
    remember = array[(j=i)];

    while(--j >= 0 && remember < array[j])
    {
      array[j+1] = array[j];
      array[j] = remember;
    }
  }

  printf("after : \n");
  for(i=0;i<size;i++)
  {
    printf("%2d ", array[i]);
  }
  printf("\n");
}

int main(void)
{
  int num[] = {10,1,3,7,5,6,9,8,2,4};

  insertion_sort(num, (sizeof(num)/sizeof(int)));


  return 0;
}

 

 

* Note

 

Stable sort이란?

=> 같은 값이 2개 이상 존재하는 리스트를 정렬할 시 Stable sort는 같은 값도 순서대로 정렬될 수 있는 방법이다.

int list[] = {5, 2, 4(첫번째), 1, 4(두번째)};

=> 정렬을 진행하면아래 와 같이 정렬되는 것을 의미함
int list[] = {1, 2, 4(첫번째), 4(두번째), 5};

in-Place이란?

추가적인 메모리가 필요 없는 알고리즘을 뜻합니다.

10개의 list가 있다면 10개의 list에 해당하는 메모리만 사용하고 추가적인 메모리 할당이 필요 없음을 뜻합니다.

 

Comparison이란?

값을 비교하는 정렬 알고리즘을 의미합니다.