삽입 정렬 (Insertion Sort)

• 주어진 데이터를 하나씩 뽑아, 나열된 데이터들이 항상 정렬된 형태를 가지도록, 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식

• 시간복잡도 O(n²)

function insertionSort (array) {
  let temp, j;
  for (let i=1; i<array.length; i++) {
    temp = array[i]; // 새로운 숫자를 선택함
    for (j = i-1; j >= 0 && temp < array[j]; j--) { 
      // 선택한 숫자를 이미 정렬된 숫자들과 비교하며 넣을 위치를 찾는 과정
      // 선택한 숫자가 정렬된 숫자보다 작으면 한 칸씩 뒤로 밀어낸다
      array[j + 1] = array[j];
    }
    array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자를 넣어준다.
  }
  return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]