삽입 정렬 (Insertion Sort)
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
평균 시간 복잡도는 O(n²)이지만, 거의 정렬되어 있는 상태에서는 O(n)에 가까운 매우 빠른 속도를 보여줍니다.
function insertionSort(arr) {
const n = arr.length;
console.log("초기 배열:", arr);
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
// key보다 큰 값들은 한 칸씩 오른쪽으로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", insertionSort(arr));