Insertion Sort

삽입정렬이란?

• 적은 수의 요소를 정렬하기에 효율적이고 단순한 정렬
• 카드순서를 정리하듯 순서를 보고 끼워 넣어 정렬하는 것

---

예를 들어, 왼손에는 2,4,5,10의 카드를 쥐고 있고 테이블에 7의 카드가 있는 상태인 경우,
7의 카드를 가져올 때, 5와 10 사이에 끼워넣어 왼손에 2,4,5,7,10의 순서로 손에 쥘 것입니다.
이처럼 어떤 요소를 이미 정렬이 되어 있는 요소들에 넣을 때 정렬이 되어 있는 요소들의 순서를 파악해 삽입하는 정렬을 삽입정렬이라 합니다.

---

삽입정렬의 구체적 개념

두번째 자료부터 시작해 앞의 자료들과 비교한 뒤, 삽입할 위치를 찾는다.

2번째는 1번째와 비교
3번째는 2번째, 1번째와 비교
4번째는 3번째, 2번째, 1번째와 비교

이런식으로 비교한다.
조건에 따라 자료들을 한칸씩 이동시키며 삽입할 위치를 찾는다.

2번째 자료부터 차례로 정렬한다. -> 이후에 처리할 자료보다 '앞에 있는 자료들'은 '이미 정렬되어 있는 자료들'인 것이다.

---

삽입정렬 예제

7, 6, 3, 2, 5 를 오름차순 정렬하는 예제에 대해 설명하겠습니다.

1) 두번째에 위치한 6을 temp에 저장(위로 잠깐 빼두는 것으로 생각한다.)
2) 6을 첫번째 7과 비교
3) 7이 크므로 7의 위치를 한칸 뒤로
4) temp에 있는 6을 첫번째 위치로
-->  6, 7, 3, 2, 5

1) 세번째에 위치한 3을 temp에 저장
2) 3을 두번째 7과 비교
3) 7이 크므로 7의 위치를 한칸 뒤로
4) 3을 첫번째 6과 비교
5) 6이 크므로 6의 위치를 한칸 뒤로
6) temp에 있는 3을 첫번째 위치로
--> 3, 6, 7, 2, 5

1) 네번째에 위치한 2를 temp에 저장
2) 2를 세번째 7과 비교
3) 7이 크므로 7의 위치를 한칸 뒤로
4) 2를 두번째 6과 비교
5) 6이 크므로 6의 위치를 한칸 뒤로
6) 2를 첫번째 3과 비교
7) 3이 크므로 3의 위치를 한칸 뒤로
8) temp에 있는 2를 첫번째 위치로
--> 2, 3, 6, 7, 5

1) 다섯번째에 위치한 5를 temp에 저장
2) 5를 네번째 7과 비교
3) 7이 크므로 7의 위치를 한칸 뒤로
4) 5를 세번째 6과 비교
5) 6이 크므로 6의 위치를 한칸 뒤로
6) 5를 두번째 3과 비교
7) 3이 작으므로 3의 위치는 옮기지 않는다.
8) temp에 있는 5를 세번째 위치로
--> 2, 3, 5, 6, 7

위와 같은 일련의 과정을 거친다.

---

삽입정렬 Javascript로 구현하기

let insertionSort = function(array){
  for(let i = 1 ; i < array.length ; i++){
    let temp = array[i];
    
    for(let j = i-1 ; j >= 0 ; j--){
      if(array[j] > temp){
        array[j+1] = array[j];
        console.log(array);
      }
      if(array[j-1] === undefined || array[j-1] < temp){
        array[j] = temp;
        console.log(array);
        break;
      }
    }
  }
};

let a = [7,6,3,2,5];

insertionSort(a);

콘솔에 찍히는 결과

[ 7, 7, 3, 2, 5 ] // i = 1 (temp에 6 저장)
[ 6, 7, 3, 2, 5 ]

[ 6, 7, 7, 2, 5 ] // i = 2 (temp에 3 저장)
[ 6, 6, 7, 2, 5 ]
[ 3, 6, 7, 2, 5 ]

[ 3, 6, 7, 7, 5 ] // i = 3 (temp에 2 저장)
[ 3, 6, 6, 7, 5 ]
[ 3, 3, 6, 7, 5 ]
[ 2, 3, 6, 7, 5 ]

[ 2, 3, 6, 7, 7 ] // i = 4 (temp에 5 저장)
[ 2, 3, 6, 6, 7 ]
[ 2, 3, 5, 6, 7 ]

---

삽입정렬 시간복잡도

삽입정렬의 경우 Input의 사이즈, Input의 순서에 따라 running time이 매우 길어질 수 있다.

Best Case : T(n) = O(n)

• 이미 정렬이 되어 있는 배열의 경우

Worst Case : T(n) = O(n^2)

• 역순으로 정렬되어 있는 배열의 경우

---