30. Insertion Sort

삽입 정렬(Insertion Sort)은 각각의 원소를 이전에 정렬한 앞쪽 원소들과 비교해서 맞는 위치에 추가하는 과정을 반복한다. 원소를 앞쪽에 추가하면 이전에 정렬된 원소 중 이번 원소가 추가될 자리 뒤쪽에 있는 원소들의 위치가 하나씩 뒤로 밀리게 되므로 단순히 각각의 원소를 바로 앞 원소부터 차례로 비교하면서 비교 관계가 바뀌었다면 서로 바꾸는 식으로 구현하면 된다.

 

다음은 이전 글에 예시로 나온 정렬을 C++에서 삽입 정렬로 구현한 코드이다.

for(k = 0; k++ < n;)
{
    for(i = k; i > 1 && a[i - 1] > a[i]; i--)swap(a[i - 1], a[i]);
}

이 코드는 굉장히 간단하고, 시간복잡도가 $O(n^2)$이라서 앞의 두 코드보다 약간 더 빠른 경우가 많다. 하지만 이건 코드 구조에 의한 것이지 시간복잡도 상으로는 여전히 입력이 커지면 느려진다는 점을 잊지 않아야 한다.

 

다음은 삽입 정렬 과정을 시뮬레이션한 것이다.

이것은 좀더 알기 쉬운 예시이다.

 

→ solved.ac tag: sorting