삽입정렬
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
JavaScript 삽입 정렬 구현
function insertionSort(arr) {
for (let i = 1 ; i < arr.length; i++) {
let j = i - 1;
key = arr[i];
while (arr[j] > key && j >= 0) { // 비교할 값이 현재 비교중인 원소보다 크면
arr[j + 1] = arr[j] // 비교할 값을 한 칸 뒤로 미루고 (어차피 뒤에 있는 j + 1은 i이거나 이미 복사된 값이기 때문에 덮어써도 됨)
j--;
}
// 마지막 j는 key 보다 작은 값이기 때문에 덮어쓰면 안되고 그 바로 다음 자리에 삽입
arr[j + 1] = key;
}
return arr;
}
insertionSort([5, 3, 2, 4, 1]);
동작 순서
| i | 비교할 값 | 이미 정렬된 부분 | 삽입할 위치 | arr |
|---|---|---|---|---|
| 1 | 3 | [5] | 0 | [3, 5, 2, 4, 1] |
| 2 | 2 | [3, 5] | 0 | [2, 3, 5, 4, 1] |
| 3 | 4 | [2, 3, 5] | 2 | [2, 3, 4, 5, 1] |
| 4 | 1 | [2, 3, 4, 5] | 0 | [1, 2, 3, 4, 5] |
특징
- 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번재 항목은 제거되어 정확한 위치에 삽입된다.
- 배열이 길어질수록 효율이 떨어진다.
- 구현은 간단하다.
- 대부분의 원소가 이미 정렬되어 있는 상태라면 효율이 매우 좋다.
- 레코드의 수가 적을수록 유리하다.