Insertion Sort

개념

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입하는 삽입 위치 뒤에 위치한 원소들은 자리가 밀린다.

Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘

• 공통점 : k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다.
• 차이점 : Selection Sort는 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 Insertion Sort는 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색한다.

과정

1. 늘 왼쪽 원소와 비교하게 되므로 두 번째 위치부터 탐색을 시작함.
2. 비교 대상의 왼쪽에 위치한 원소들과 비교하여 비교 대상보다 큰 수가 있다면 그 앞에 삽입
3. 이전 원소들과의 비교가 끝나면 다음 위치로 이동하여 반복

시간복잡도

Big-O : O(n^2)

Big-Ω : Ω(n)

모두 정렬이 되어있는 경우 한번씩만 비교하게 되므로 Ω(n)의 시간복잡도를 가지게 된다.

장단점

장점

• 알고리즘이 단순함.
• 메모리 절약
  정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간 불필요
  (in-place sorting 제자리정렬)

단점

• 최악의 경우 시간복잡도가 비효율적

특징

Stable

중복 데이터가 있는 경우 데이터가 교환되지 않고 정렬이 다 끝난 후에도 기존 중복 데이터의 순서가 유지되는 정렬

코드

function insertionSort (array) {
  for(let i=1; i<array.length; i++){
    let swap = array[i];
    let prev = i-1;
    while(prev>=0 && array[prev]>swap){
      array[prev+1] = array[prev];
      prev--;
      }
  array[prev+1] = swap;
    console.log(`${i}회전 : ${array}`);
  }
  return array;
}
console.log(insertionSort([5,7,3,4,1,6,2]));

참고자료
CS50
https://medium.com/@peterlin5301997/bubble-sort-5a66156c942e
https://im-developer.tistory.com/133