[JS 알고리즘] 삽입 정렬(Insertion sort)

삽입 정렬의 작동원리

• 삽입 정렬은 루프를 돌면서 정렬한 요소를 왼쪽에 쌓아가면, 각 요소를 보면서 이미 정렬되어 있는 절반에서 어디로 가야 하는지 찾고 그곳에 삽입한다.
  

삽입 정렬 의사 코드

• 배열에서 두 번째 요소(그 다음 루프에서는 세 번째...루프 끝까지)를 선택하여 루프를 시작한다.
  - 이제 두 번째 요소를 이전 요소와 비교하고 더 작은 경우 교체한다.
  - 다음 요소로 진행하고 순서가 잘못된 경우 왼쪽에 정렬된 부분에서 반복문을 돌려 거기서 해당 요소가 있어야 할 위치에 배치한다.
• 배열이 정렬될 때까지 위 작업을 반복한다.

삽입 정렬 코드

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    let j;
    for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  return arr;
}

console.log(insertionSort([4, 3, 2, 1, 5, -5, 20, 17]));

삽입 정렬의 성능

• Best Case : $O(n)$
  • 삽입 정렬은 완전히 무작위인 배열보다 거의 정렬되어 있는 배열에서 더 빠르다.
    • 온라인에서 실시간으로 데이터를 받고 있고 이를 모아서 정렬해야 하는 코드를 작성해야 할 때, 삽입 정렬은 배열의 한 쪽에 정렬된 부분을 두고 한 번에 하나씩 요소들을 삽입하는 방식이기 때문에 이런 경우 사용하는 것이 적절할 수 있다.
• Worst Case: $O(n^2)$
• Average Case : $O(n^2)$

버블, 선택, 삽입 정렬 비교

• 평균적인 시간 복잡도는 모두 $O(n^2)$으로 동일하나, 각각의 Best Case에서 선택 정렬만 $O(n^2)$이고 나머지 버블 정렬과 삽입 정렬은 $O(n)$이다.
  • 버블, 선택, 삽입 정렬도 데이터의 크기가 작을 경우에는 생각보다 빠르고 괜찮을 수 있다.