🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
정렬 - 삽입 정렬
📍 삽입 정렬(Insertion Sort)
👉🏻 배열을 두 영역으로 나누어 진행(정렬된/되지 않은 영역)
[4, 1, 5, 3, 6, 2] // 정렬되지 않은 영역에서 데이터를 꺼내 정렬된 영역 사이에 삽입
<--- 영역 --->
[4, 1, 5, 3, 6, 2] // 첫 번째 숫자인 4만 정렬되어 있다고 가정
_ _
[4, 1, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 1을 정렬된 데이터 4와 비교한 뒤, 4보다 작으므로 삽입
[1, 4, 5, 3, 6, 2]
<-- 영역 -->
[1, 4, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 5를 정렬된 데이터의 가장 오른쪽부터 비교
[1, 4, 5, 3, 6, 2]
<- 영역 ->
[1, 4, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 3을 정렬된 데이터의 가장 오른쪽부터 비교
_ _
[1, 4, 5, 3, 6, 2] / 5보다 3이 작으므로 정렬된 영역 중 더 왼쪽 데이터와 비교
_ _
[1, 4, 5, 3, 6, 2] // 4보다 3이 작으므로 정렬된 영역 중 더 왼쪽 데이터와 비교
_ _
[1, 4, 5, 3, 6, 2] // 1보다는 크므로 삽입
[1, 3, 4, 5, 6, 2]
-영역-
[1, 3, 4, 5, 6, 2]
...
[1, 2, 3, 4, 5, 6] // 정렬 끝
👉🏻 선택 정렬은 정렬되지 않은 영역에서 가장 작은 데이터를 찾아 왼쪽으로 정렬
👉🏻 삽입 정렬은 정렬된/정렬되지 않은 영역 2개로 나눈 뒤에 정렬되지 않은 데이터를 정렬된 데이터 오른쪽부터 하나씩 비교해 감
📍 삽입 정렬의 구현
[ insertion_sort.mjs ]
function InsertionSort(arr) {
// 정렬되지 않은 영역의 첫 번째부터 마지막 원소를 순회하는 for문
for(let i = 1; i < arr.length; i++) {
// 1부터 시작하는 이유는 '첫 번째 원소를 이미 정렬된 영역'으로 보기 때문임
let insertingData = arr[i];
// j: 삽입 위치
let j;
// 정렬된 영역의 마지막 원소는 정렬되지 않은 원소의 한 칸 앞
for(j = i -1; j >= 0; j--) { // 정렬된 영역을 오른쪽부터 역순 진행
if(arr[j] > insertingData) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = insertingData;
}
}
let arr = [4, 1, 5, 3, 6, 2];
console.log("===== 정렬 전 =====");
console.log(arr);
InsertionSort(arr);
console.log("===== 정렬 후 =====");
console.log(arr);
👉🏻 삽입 정렬의 성능 O(n^2)
📍 삽입 정렬의 장단점
👉🏻 장점: 이해가 쉽고 구현이 간단함
👉🏻 단점: 성능이 좋지 않음