삽입 정렬이란?

삽입 정렬은 이미 정렬된 데이터 범위에 아직 정렬이 안 된 데이터를 적절한 위치에 삽입시켜 정렬하는 알고리즘이다.

삽입 정렬은 시간 복잡도가 O(n^2)이지만 구현이 쉽다.

삽입 정렬의 과정
1. 현재 인덱스에 있는 데이터를 선택
2. 현재 선택한 데이터가 정렬된 데이터 범위 중에서 삽입될 위치를 탐색
3. 삽입 위치와 현재 선택한 데이터를 swap 해주고 index++
4. 전체 데이터의 크기만큼 인덱스가 커질 때까지(선택할 데이터가 없을 때까지) 반복

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) { // [5,4,3,2,1]
    let insert_point = i - 1; //0
    let insert_value = arr[i]; //4

    while (insert_point >= 0 && arr[insert_point] > insert_value) { //0  5>4
      arr[insert_point + 1] = arr[insert_point]; //arr[1]=arr[0] //[5,5,3,2,1]
      insert_point--; //-1
    }
    arr[insert_point + 1] = insert_value; //arr[0]=4 [4,5,3,2,1]
  }
  return arr;
}

insert_value에 arr[i]를 담아두었다가 삽입할 위치를 탐색한 후에 넣어준다.