[C] 삽입정렬 개념, 알고리즘, 코드 정리

삽입정렬

---

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식입니다.

배열이 길어질수록 효율이 떨어지지만, 구현이 간단합니다.

시간복잡도는 O(n^2) 입니다.

삽입정렬 알고리즘

---

1. 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다.

2. 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다.

3. 위의 작업을 정렬이 끝날때까지 반복합니다.

삽입정렬 예제

---

25 를 앞의 리스트와 비교하여 적절한 위치에 삽입합니다.

31	25	12	22	11
25	31	12	22	11

12 를 앞의 리스트와 비교하여 적절한 위치에 삽입합니다.

25	31	12	22	11
12	25	31	22	11

22 를 앞의 리스트와 비교하여 적절한 위치에 삽입합니다.

12	25	31	22	11
12	22	25	31	11

11 을 앞의 리스트와 비교하여 적절한 위치에 삽입합니다.

12	22	25	31	11
11	12	22	25	31

삽입정렬 소스

---

#include <stdio.h>

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ){
      data[j+1] = data[j];
      data[j] = remember;
    }
  }
}

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

  insertion_sort(list, 10);

  for(i=0; i<10; i++){
    printf("%d  ", list[i]);
  }
  return 0;
}

    위키에 첨부된 소스에서 main 함수를 넣어 완성시킨 코드입니다.