삽입 정렬(Insertion Sort)

References

이번 글은 아래 자료를 참고하여 작성하였습니다.
Insertion Sort on Khan Academy

Insertion Sort

function insert(array, rightIndex, value) {
  // let temp;
  // for (let i = rightIndex; i >= 0; --i) {
  //   if (value < array[i]) {
  //     temp = array[i];
  //     array[i] = value;
  //     array[i + 1] = temp;
  //   }
  // }

  for (let i = rightIndex; i >= 0 && array[i] > value; --i) {
    array[i + 1] = array[i];
    array[i] = value;
  }
}

function insertionSort(array) {
  for (let i = 1; i < array.length; ++i) {
    insert(array, i - 1, array[i]);
  }
  return array;
}

const array = [3, 5, 7, 11, 13, 2, 9, 6];
console.log(insertionSort(array)); // [2, 3, 5, 6, 7, 9, 11, 13]

insertionSort를 통해 주어진 배열을 입력값으로 탐색하면서 rightIndex 범위 내의 값들 중 입력값보다 탐색값이 크다면 탐색값의 index를 1만큼 증가시키고, array[i]에 있던 값을 value로 바꾼다. 이 작업을 반복하면 주어진 배열이 오름차순으로 정렬된다.