정렬 알고리즘 - 삽입 정렬

삽입 정렬(Insertion Sort)

• 왼쪽에서 오른쪽의 순서로 비교를 진행하여 요소를 정렬하는 방식.

시간복잡도

• 최선의 경우 : O(n), 이미 정렬이 되어있는 경우
• 최악의 경우 : O(n^2), 정렬이 하나도 안되어있는 경우
  
  

장점

• 삽입 정렬 역시 버블 정렬과 같이 in place 알고리즘으로 메모리가 절약된다.
• 구현이 매우 간단하며 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수 있다.
  
  

단점

• 삽입 정렬 역시 자료의 개수가 많아질수록 성능이 매우 떨어진다.
  
  

구현

'use strict';

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const cur = arr[i];
    let leftIdx = i - 1;

    while (leftIdx >= 0 && arr[leftIdx] > cur) {
      [arr[leftIdx], arr[leftIdx + 1]] = [arr[leftIdx + 1], arr[leftIdx]];

      leftIdx--;
    }

    console.log(`${i}회전 : ${arr}`);
  }

  return arr;
}

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