- 삽입 정렬은 배열의 앞에서부터 시작하여 자신의 앞에 있는 모든 요소와 크기 비교를 통해 자신에게 맞는 위치에 요소를 삽입한다.
- 삽입 정렬은 O(N^2)이다. O(N^2)은 안좋지만 사용하는 이유는 알고리즘 자체가 간단하다.
- 3을 [6]의 적절한 위치에 삽입하고 다음으로는 5를 [3, 6]의 적절한 위치에 삽입한다. 다음으로는 1을 [3, 5, 6]의 적절한 위치에 삽입하고 이 방식으로 삽입 작업이 반복된다.
- 이전 값보다 큰 값이면 그대로 있는다.
예시)
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let val = array[i];
let j = i - 1;
while (j >= 0 && array[j] > val) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = val;
}
return array;
}
let array = [6, 3, 5, 1, 9, 4, 8, 2, 7];
console.log(insertionSort(array));const insertionSort = (array) => {
for (let i = 1; i < array.length; i++) {
let val = array[i];
let j = i - 1;
while (j >= 0 && array[j] > val) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = val;
}
return array;
};
let array = [6, 3, 5, 1, 9, 4, 8, 2, 7];
console.log(insertionSort(array));
// val = 6
// j = 0
// array [6 6 5 1 9 4 8 2 7]- 다른 메모리 공간이 필요하지 않고 안정 정렬(stable sort)이며 시간 복잡도는 O(N)이다. 단점으로 최악의 시간 복잡도는 O(N^2)가 될 수 있으며 배열이 커질수록 비효율적이다.