자바스크립트 정렬 알고리즘 4 : Insertion Sort

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

앞서 배운 Bubble Sort, Selection Sort의 경우 사실 교육적 목적을 제외하면, 실무에서 사용할 일은 거의 없다고 한다.

그러나 Insertion Sort는 경우에 따라서 가장 빠른 속도를 낼 수 있기 때문에 정확히 알아둬야 한다.

 

Insertion Sort(삽입 정렬)를 사용하는 상황은 아래 조건이 충족될 때이다. 아래 조건에서는 그 어떤 정렬 알고리즘보다 Insertion Sort가 가장 빠른 속도를 낼 수 있다. 동시에 공간 복잡도 또한 O(1)이므로 아래 상황에는 Insertion Sort 사용을 고려해야 한다.

1. data의 규모와 크기가 작은 경우
2. data가 거의 정렬이 되어 있는 경우

 

☞ Insertion Sort의 로직

 

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < arr[0]) arr.unshift(arr.splice(i, 1)[0]);
    else {
      for (let k = 1; k < i; k++) {
        if (arr[i] > arr[k-1] && arr[i] < arr[k]) {
          arr.splice(k, 0, arr.splice(i, 1)[0]);
        }
      }
    }
  }
  return arr;
}