정렬 알고리즘 - 삽입 정렬

삽입 정렬은 버블 정렬, 선택 정렬과 유사한 정렬 알고리즘 패턴이다. 삽입 정렬은 배열을 순회하면서 이미 정렬된 부분과 비교하여 올바른 위치에 삽입하면서 정렬하는 패턴이다.

1. 배열의 두 요소를 최초 값으로 설정한다.
2. 이때 선택된 값 중 첫 번째 값은 이미 정렬된 것으로 간주하기 때문에, 두 번째 값과 첫번째 값을 비교하여 두번째 값을 올바른 위치에 삽입한다.
3. 정렬 후 그 다음 값을 비교하여 올바른 위치에 해당 값을 삽입한다.
4. 모든 배열을 순회할 때까지 위 과정을 반복한다.

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

console.log(insertionSort([312, 32, 66, 12, 1, 8, 41, 12]));

첫 번째 요소는 이미 정렬된 값으로 간주하기 때문에 첫 번째 값의 인덱스를 배열의 두 번째 값인 1로 설정한다. 이 값은 배열을 순회하면서 앞의 값과 크기를 비교한다. currentVal을 기준으로 앞의 값이 현재 값보다 크면, currentVal의 뒤에 해당 값을 삽입한다.

currentVal을 기준으로 앞의 값이 현재 값보다 크면 currentVal의 뒤에 해당 값을 삽입한다. 그리고 currentVal을 한 칸 뒤로 옮기고 앞선 패턴을 반복한다.