[자료 구조와 알고리즘] 정렬 - 삽입 정렬

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

정렬 - 삽입 정렬

 

 

 

 

📍 삽입 정렬(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) 

 

 

 

📍 삽입 정렬의 장단점

👉🏻 장점: 이해가 쉽고 구현이 간단함

👉🏻 단점: 성능이 좋지 않음