삽입 정렬(Insert sort)

: 두번째 element부터 시작해 본인의 앞 element들과 비교하면서(계속 swap하면서) 본인의 위치를 찾아감.

• 최선의 경우 : 이동 없이 1번의 비교만 이루어지는 경우(이미 정렬되어 있는 경우)
  • O(N) 시간복잡도를 갖는다.
• 최악의 경우 : 완전 역순으로 되어있을 때
  • O(n^2) 시간복잡도를 갖는다.
  • 이때는 이동 횟수도 O(N^2)
• 장점
  • 안정적인 정렬방법 (같은 값에 대해선 change 하지 않고 다음 원소의 정렬로 넘어감)
  • 이미 거의 정렬되어있는 경우에 매우 효율적일 수 있다.
    • n 값이 작은 경우에도 효율적이다(n < 16을 기준으로 선택한다고 한다)
  • 참조 지역성의 효과를 매우 잘 얻을 수 있다.
• 단점
  • 많은 이동을 포함
    • 바로 앞의 것과 비교해 옮길만 하면 그냥 바꿔버림
    • 레코드 수가 많고 레코드 크기가 클경우 부적합

코드

void insertSort(int data[], int size) {
    for(int i = 1; i < size; i++) {
        for(int j = i; j > 0; j--) {
            if(data[j - 1] >= data[j])
                break;
            int tmp = data[j - 1];
            data[j - 1] = data[j];
            data[j] = tmp;
        }
    }
}

Reference)

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

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html