Insertion Sort (삽입 정렬)

Insertion Sort란

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 배열을 정렬한다.

 

 

function swap(arr, idx1, idx2) {
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

// insertionSort가 아니라 이상하게 bubble sort처럼? 해버림
// function insertionSort(arr) {
//   for (let i = 1; i < arr.length; i++) {
//     for (let j = i; j > 0; j--) {
//       if (arr[j] < arr[j - 1]) {
//         swap(arr, j, j - 1);
//       }
//     }
//   }
//   return arr;
// }

function udemyInsertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    let currValue = arr[i];
    for (var j = i - 1; j >= 0 && arr[j] > currValue; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currValue;
  }
  return arr;
}
// console.log(insertionSort([3, 44, 38, 5, 47]));
console.log(udemyInsertionSort([3, 44, 38, 5, 47]));

 

 

Insertion Sort의 Big O

데이터가 거의 정렬된 경우 사용하면 좋다.

반대로 데이터가 내림차순으로 정렬되어 있는 경우 오름차순으로 정렬하고자 할 때 성능이 제일 안좋다. 

온라인 알고리즘 (데이터가 들어오는 대로 작동하는 알고리즘) 일 경우 

-> 새로운 데이터를 수신하므로 전체 배열을 한번에 정렬할 필요가 없어 이때는 삽입정렬을 사용하는 것이 유리하다.