삽입 정렬(Insertion Sort)란?
삽입 정렬은 배열을 정렬하기 위한 매우 단순한 비교 정렬(comparison sort) 방식입니다. 비교 정렬은 현재 정렬하려는 값을 배열 내 다른 값들과 비교하여 적절한 위치를 찾는 방식으로 동작합니다. 삽입 정렬은 한 번에 한 개의 항목씩 처리하며, 각 항목을 반복적으로 올바른 자리에 배치해 나가므로써 최종적으로 정렬된 배열을 얻습니다.
사실 삽입 정렬은 힙 정렬(heap sort)이나 병합 정렬(merge sort) 같은 고급 알고리즘만큼 효율적이지 않으며, 대규모 데이터를 다룰 때는 최선의 선택이 아닙니다. 하지만 낮은 숨은 상수(hidden constant) 덕분에 작은 크기의 배열을 처리할 때는 힙 정렬이나 퀵 정렬 같은 고급 알고리즘보다 오히려 더 나은 성능을 보여주기도 합니다.
삽입 정렬은 배열의 왼쪽에서 오른쪽으로 이동하며 진행됩니다. 현재 항목을 '키(key)'로 삼고, 해당 키 왼쪽에 있는 값들을 검색하여 키가 실제로 위치해야 할 자리를 찾아낸 뒤 그곳에 삽입하는 방식입니다.
알고리즘 동작 과정
다음 예제에서 정렬 대상 배열은 0, -3, 5, 8, 2, 7, 6입니다.
- 반복 0 — 첫 번째 반복에서는 아직 정렬되지 않은 원본 배열 0, -3, 5, 8, 2, 7, 6만 존재합니다.
- 반복 1 — 이번 반복의 키는 인덱스 1의 값인 -3입니다. 삽입 정렬은 키를 키 왼쪽의 값들과 비교하며 진행합니다. -3이 0보다 작으므로 0의 왼쪽으로 이동하게 되고, 배열은 -3, 0, 5, 8, 2, 7, 6이 됩니다.
- 반복 2 — 이번 반복의 키는 5(인덱스 2의 값)입니다. 키가 왼쪽의 -3과 0과 비교되어 이미 정렬된 자리에 놓이므로, 반복 2 이후 배열은 -3, 0, 5, 8, 2, 7, 6으로 유지됩니다.
- 반복 3 — 이번 반복의 키 값 8은 왼쪽 요소들과 비교되며, 결과 배열은 -3, 0, 5, 8, 2, 7, 6입니다.
- 반복 4 — 이번 반복의 키 값 2는 왼쪽 값들과 비교되어 정렬된 위치에 배치됩니다. 따라서 반복 4 이후 배열은 -3, 0, 2, 5, 8, 7, 6이 됩니다.
같은 방식으로 모든 반복이 끝나면 최종적으로 정렬된 배열은 -3, 0, 2, 5, 6, 7, 8이 됩니다.
시간 복잡도 및 특징
삽입 정렬의 평균 및 최악의 시간 복잡도는 O(n²)이지만, 이미 정렬된 배열이 들어오는 최선의 경우에는 O(n)으로 매우 빠르게 동작합니다. 또한 추가 메모리가 거의 필요 없는 제자리(in-place) 정렬이며, 값이 같은 요소들의 상대적 순서를 유지하는 안정 정렬(stable sort)이라는 장점도 있습니다.
예제 코드
<html>
<head>
<script>
function iSort(array) {
for (var p = 1; p < array.length; p++) {
if (array[p] < array[0]){
array.unshift(array.splice(p,1)[0]);
}
else if (array[p] > array[p-1]){
continue;
}
else {
for (var q = 1; q < p; q++) {
if (array[p] > array[q-1] && array[p] < array[q]){
array.splice(q,0,array.splice(p,1)[0]);
}
}
}
}
return array;
}
document.write(iSort([0,-3,5,8,2,7,6]));
</script>
</body>
</html>실행 결과
-3,0,2,5,6,7,8