삽입 정렬 (Insertion Sort)

: 제자리 정렬
: 안정 정렬
: 시간 복잡도는 평균 O(n^2)

내 앞에 있는 것이 크면 바꾸고 (뒤로 밀어서 적절한 위치에 삽입)
아니면 그대로

---

특징

• 제자리 정렬(in-place sort)
  이미 주어진 원소들을 옮긴 뒤 적절한 위치에 원소를 삽입하는 연산을 반복하는데, 이 과정에서 원소들을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 원소가 저장되는 공간과 루프 변수 정도에 불과하다

• 안정 정렬(stable)
  동일한 두 원소는 이미 위치가 정해져있어서 바뀌지 않음
  (현재보다 앞에 있는 것이 클 때만 바꾸기 때문에)

• 시간 복잡도는 평균 O(n^2)
  최선은 비교하는 것만 (n-1)번 해서 O(n)
  평균은 1 + 2 + ... + (n-1) = n*(n-1)/2 = O(n^2)

---

소스코드

#include <stdio.h>

void insertion_sort(int *arr, int n)
{
    int i;
    int j;
    int num;

    i = 1;
    j = 0;
    while (i < n)
    {
        num = arr[i];
        j = i - 1;
        while (j >= 0 && num < arr[j])
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j+1] = num;
        i++;
    }
}

---

참고

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
C언어로 췹게 풀어쓴 자료구조