삽입 정렬 (Insertion Sort)

: 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘

의사 코드

function insertionSort(arr) {
	반복문 (배열을 순회하며 arr[i]와 arr[i - 1]을 비교할 것이다.) {
      let 삽입할 숫자 = arr[i]
      let j = i 바로 앞에 있는 숫자, 즉 i -1
      
      삽입할 숫자와 arr[j]를 비교하여, 
      
      1. arr[j]가 더 크다면 arr[j]를 뒤로 한 칸 옮길 것이고,
    
      하지만 i 앞에는 정렬된 숫자가 여러 개 있을 수도 있으므로, 반복문을 돌려야한다.
      반복문 (j가 0보다 크고, arr[j]보다 삽입할 숫자가 작다면) {
        arr[j]를 뒤로 한 칸 옮긴다.
        j를 1 감소시켜준다. // 점점 앞으로 가면서 j가 0이 될 때까지 계속 비교할 수 있도록
      }
    
      2. 삽입할 숫자가 더 크다면 arr[j] 뒤에 삽입할 숫자를 위치시킬 것이다.
    }
  정렬된 배열을 리턴한다.
}

---

풀이

function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let numToInsert = arr[i];
    let j = i - 1;
    
    while (j >= 0 && arr[j] > numToInsert) {
      arr[j + 1] = arr[j];
      j--;
    }
    
   	arr[j + 1] = numToInsert; // arr[j] < arr[i]인 경우
  }
  return arr;
}

삽입 정렬은 O(n²)의 시간복잡도를 가진다.

---

풀면서 궁금했던 점

변수 numToInsert에 arr[i]를 할당해서 사용하는 게 아니라, 그냥 arr[i]를 사용하면 안되는걸까?

numToInsert에 arr[i]를 저장하지 않고, 그냥 arr[i]로 할 경우,
arr[j + 1] = arr[j]; 부분에서 arr[i]의 값이 arr[j]로 덮어씌워져 버리기 때문에, 꼭 변수를 만들어서 arr[i] 값을 저장해두어야 한다.