삽입 정렬

삽입 정렬이란?

Swfung8, CC BY-SA 3.0, via Wikimedia Commons

삽입 정렬(Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 비교하면서 자리를 교환(swap)하는 정렬 방법이다.

삽입 정렬의 과정

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫번째 타겟은 두번째 원소부터 시작)
2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.
3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

위와 같은 삽입 정렬의 과정을 토대로 삽입 정렬의 전체적인 과정에 대해서 설명하자면 다음과 같다.

Muhamed Al-Humaid at Danish Wikipedia, Public domain, via Wikimedia Commons

(a) : 첫번째 타겟은 두번째 원소부터 시작하므로 첫번째 타겟은 7이 된다. 7 이전 위치에 있는 원소인 3과 비교했을 때 3이 더 작으므로 위치를 스왑하지 않는다.

(b) : 두번째 타겟인 2와 이전 위치의 원소인 7,3의 순서대로 비교하며, 타겟보다 원소가 클 경우 원소를 뒤로 미루고 마지막 원소 위치에 타겟을 넣는다.

(c) : 세번째 타겟인 5와 이전 위치의 원소를 순서대로 비교한다. 5보다 작은 원소가 나오면 비교를 중단한다.

(d) : 네번째 타겟인 1과 이전 위치의 원소를 순서대로 비교한다.

(e) : 다섯번째 타겟인 4와 이전 위치의 원소를 순서대로 비교한다.

(f) : 삽입 정렬을 통한 오름차순 정렬 완료

삽입 정렬의 특징

• 데이터를 비교하면서 찾기 때문에 비교 정렬 이다.
• 정렬할 대상이 되는 데이터 이외에는 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬 (in-place sort) 이다.
• 정렬을 하기 전에서 같은 key값을 가진 원소의 순서가 정렬 후에도 유지되는 안정 정렬 이다.

시간복잡도

• 최악의 경우 (역순으로 정렬된 경우) 선택정렬과 마찬가지로 $O(N^2)$ 이다.
• 정렬이 거의 되어있는 경우는 한번씩만 비교하므로 $O(N)$의 시간복잡도를 가지게 된다.

삽입 정렬이 가장 효율적인 정렬 알고리즘이 되는 경우

거의 정렬이 되어있는 배열에 자료를 하나씩 삽입/제거 하는 경우 삽입 정렬이 정렬 알고리즘 중 제일 효율적인 알고리즘이 될 수 있다.

공간 복잡도

• 주어진 배열 안에서만 정렬이 이루어지는 제자리 정렬 이기 떄문에 공간복잡도는 $O(N)$ 이다.

---

코드로 구현한 삽입 정렬

C++

#include <iterator>

template<typename biIter>
void insertion_sort(biIter begin, biIter end)
{
    biIter bond = begin;
    for (++bond; bond!=end; ++bond)
    {
      typename std::iterator_traits<biIter>::value_type key = *bond;
      biIter ins = bond;
      biIter pre = ins;
      for (--pre; ins != begin && *pre > key; *ins-- = *pre--);
      *ins = key;
    }
}

Java

void insertionSort(int[] arr)
{

   for(int index = 1 ; index < arr.length ; index++){

      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

Python

def insert_sort(x):
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1] = x[j]
            j = j - 1
        x[j+1] = key
    return x

---

삽입 정렬의 장단점

장점

• 알고리즘이 단순하다.
• 추가적인 메모리 소비가 작다.
• 거의 정렬 된 경우 매우 효율적이고 최선의 경우 $O(N)$의 시간복잡도를 갖는다.
• 안정 정렬이 가능하다.

단점

• 비교적 많은 수들의 이동을 포함하며 비교할 수가 많고 크기가 클 경우에 적합하지 않다.
• 최악의 경우 $O(N^2)$의 시간복잡도를 갖는다.
• 데이터의 상태에 따라서 성능 편차가 매우 크다.

면접에 나올 수 있는 질문

Q. 삽입 정렬과 선택 정렬의 차이점은?

A. 삽입 정렬은 선택 정렬과 다르게 안정 정렬이고 최선의 경우 $O(N)$의 시간복잡도를 가진다는 장점이 있다.

Q. 삽입 정렬의 시간복잡도가 차이나는 이유는?

A. 삽입 정렬은 이전의 원소와 타겟 원소를 비교하면서 규칙에 맞지 않는 경우 다음 타겟으로 넘어가기 때문에 주어진 요소에 따라 다른 시간복잡도를 갖게 된다.

참고

• 삽입 정렬 - 위키피디아
• 자바 [JAVA] - 삽입 정렬 (Insertion Sort)

---

기여자

_Jongminfire
📦