[자료구조] Insert Sort (삽입 정렬)

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

 

개념

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

정렬하는 배열이 작은 경우 효율적, 배열이 길 수록 비효율적
선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠름
구현이 간단하며 Stable Sort (안정 정렬)임

1. 첫번째 원소를 리스트에 삽입
2. n번째 원소를 리스트에 적절한 위치에 삽입 (반복)

https://en.wikipedia.org/wiki/Insertion_sort

 

시간복잡도

Worst Case - 비교, 교환 O(n^2) 
Best Case - 비교 O(n), 교환 O(1)
Average Case - 비교, 교환 O(n^2)

 

예제 코드

void insertionSort(int list[], int n)
{
  int i, j, temp;

  for (i = 1; i < n; ++i)
  {
    temp = list[i];

    for (j = i - 1; j >= 0 && list[j] > temp; --j)
    {
      list[j + 1] = list[j]; 
    }

    list[j + 1] = temp;
  }
}