삽입 정렬(Insertion Sort)

큰 요소를 찾아 하나씩 이동하거나, 각 루프당 가장 작은 요소를 찾아 갱신하는 대신 각 요소를 정렬된 배열에 삽입하는 것
⇒ 루프 당 정렬된 배열 속에 하나의 항목을 삽입하여 점진적으로 정렬된 배열을 만드는 것

• 작은 데이터셋이나 거의 정렬된 데이터에서 효율적
• 큰 데이터셋에서는 비효율적

진행 과정(오름차순 기준)

1. 먼저 배열의 두번째 요소부터 선택해 반복문 수행

   → 맨 첫번째 요소는 이미 정렬되었다고 간주

2. 따라서 두번째 값부터 저렬된 배열과 비교하여 올바른 위치에 삽입하며 정렬

3. 정렬이 끝날 때까지 위 과정 반복 후 정렬된 배열 반환

구현 코드(오름차순 기준)

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = current;
    console.log(arr); 
    //[2, 9, 6, 1, 8, 3]
    //[2, 6, 9, 1, 8, 3]
    //[1, 2, 6, 9, 8, 3]
    //[2, 9, 6, 1, 8, 3]
    //[1, 2, 3, 6, 8, 9]
  
  return arr;
};

const testArr = [2, 9, 6, 1, 8, 3];
console.log(insertionSort(testArr)); 

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 최선의 경우 (O(n))
  • 평균적인 경우 (O(n²))
  • 최악의 경우 (O(n²))
• 공간 복잡도
  • O(1) (추가적인 배열 없이 원본 배열에서 정렬 수행)