삽입 정렬(Insertion Sort) 이란

삽입 정렬

처리되지 않은 데이터를 적절한 위치에 삽입하는 알고리즘이다.

 

삽입 정렬에서는 배열 첫번째 원소는 정렬되었다고 판단하며, 두번째 원소부터 어떤 위치로 들어가야 할 지 판단한다.
즉, 두번째 원소부터 시작해서 앞에 있는 원소들과 비교하며 삽입할 위치에 데이터를 삽입하며 정렬하는 알고리즘이다.

 

삽입 정렬의 과정은 다음과 같다.

 

1. N번째 인덱스의 값을 저장한다.
2. 1 ~ N-1번째 인덱스에 있는 원소들과 비교하며 적절한 위치를 찾아 삽입한다.
3. 1번 과정과 2번 과정을 반복한다.

 

gif를 통해 이해해보자.

출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 

삽입 정렬을 JS 코드를 통해 구현하였다.

  const arr = [5, 6, 3, 1, 8, 7, 2, 4];

  function insertionSort(arr){
      const len = arr.length;

      for(let i=1; i<len; i++){
          let idx = i-1;
          const tmp = arr[i];
          while(tmp < arr[idx] && idx >= 0){
              arr[idx + 1] = arr[idx];
              idx--;
          }
          arr[idx + 1] = tmp;
      };

      return arr;
  }

  console.log(insertionSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]

두번째 인덱스(i = 1)부터 탐색을 시작한다.

 

tmp 변수에 삽입할 인덱스의 값을 저장하고, idx 변수를 이용해 i의 바로 왼쪽부터 tmp 변수가 들어갈 위치를 탐색한다.

 

while문을 통해 tmp 변수보다 큰 값을 모두 우측으로 한칸씩 옮긴다.(= 인덱스를 1씩 증가시킨 위치에 값을 이동시킨다.)

tmp < arr[idx] && arr[idx-1] >= tmp 인 위치의 idx를 구한다.
(만약 tmp 변수가 가장 작은 변수라면 idx = 0에 있는 값을 idx = 1로 옮겨준다.)

 

그리고 idx + 1 위치에 tmp 변수를 삽입한다.
(현재 idx 위치는 tmp보다 작은 값이 있거나, 배열의 맨 앞의 앞인 -1을 의미한다.)
(while문에 의해 idx + 1의 위치에 있는 값과 idx + 2에 있는 값이 같으므로, idx + 1에 tmp 변수를 넣어주면 된다.)

 

즉 선택한 인덱스로부터 왼쪽에 있는 원소들과 대소를 비교하는데, 자신보다 작은 값을 가진 인덱스를 찾는다고 생각하면 되겠다.

---

삽입 정렬의 시간복잡도

평균 시간복잡도는 비교, 교환을 통해 O(N^2)를 가진다.
선택 정렬같이 이중 반복문을 수행하기 때문이다.

최악의 경우는 역으로 정렬된 경우이며 선택 정렬과 같이 n(n-1)/2 => O(n^2)를 보인다.
최선의 경우는 모두 정렬된 경우이며, 비교 O(N), 교환 O(1)로 O(N)의 복잡도를 가진다.

이미 정렬된 상태에서 삽입 정렬을 수행하면..?

• 기준에서 왼쪽 원소들과 대소를 비교하므로, 모든 원소들은 1번의 비교만으로 정렬이 수행된다.
• 그러므로 어느 위치에 삽입할지 검색하는 시간이 O(상수)시간으로 대체된다.
• 정렬을 위해 각 원소를 순회해야 하므로, O(N)의 복잡도를 가진다. 즉, O(N*k) = O(N)의 복잡도를 가진다.

---

삽입 정렬의 공간복잡도

선택 정렬과 같이 배열 내에서의 swap을 통해 구현하므로, O(N)의 복잡도이다.

---

장점

선택 정렬에 비해 구현 난이도는 높으나 더 효율적이다.
대부분이 정렬된 배열에서 특히 좋다.
주어진 배열 안에서 인덱스끼리 Swap을 통해 정렬이 수행되므로 공간 효율적이다. (= 제자리 정렬)
안정 정렬이다(=중복 값이 입력 순서와 동일하게 정렬된다.)

 

안정 정렬을 간단한 예시를 통해 이해해보자.

 

 2 3 1 5 4 5 를 삽입 정렬을 통해 정렬하면, 1 2 3 4 5 5 순서로 중복 값 순서를 유지한다.

---

단점

평균, 최악 시간복잡도가 O(N^2)이다.
배열 길이가 길어질수록 효율이 떨어진다.