주어진 데이터를 하나씩 뽑아, 나열된 데이터들이 항상 정렬된 형태를 가지도록, 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식
시간복잡도 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]
