[Udemy] 삽입 정렬(Insertion Sort)이란?

정의

배열의 과반을 점차적으로 정렬로 만들어 대상 요소를 정렬된 배열에 삽입하는 방식

첫번째 배열에서 부터 비교하면서 좌측의 정렬된 배열을 점차 늘려나간다.

기존 정렬된 배열을 재배열하지 않고 새로운 데이터를 삽입하므로

기존 정렬을 유지하면서 새로운 데이터를 정렬할 때 사용하는 것이 유용하다.

 

코드

function insertionSort(arr) {
    // 첫번째 요소를 정렬된 배열 변수에 추가한다.
    let sortedArr = [arr[0]]
    // 두번째 요소부터 반복문 시작하며 정렬된 배열에 어디에 삽입할지 비교한다.
    for (let i = 1; i < arr.length; i++) {
        const currVal = arr[i]
        for (let j = i - 1; j >= 0 && sortedArr.length === i; j--) {
            if (sortedArr[j] > currVal && (sortedArr[j-1] ?? -Infinity) < currVal) {
                sortedArr.splice(j,0,currVal)
            } else if (sortedArr[j] < currVal) {
                sortedArr.splice(j+1,0,currVal)
            }
        }
    }
    return sortedArr;
}

처음에 내가 생각한 방법은 정렬된 배열을 생성하고 삽입을 위해서 splice를 사용하는 것이었다.

 

최적화 코드

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const currVal = arr[i]
        for (let j = i - 1; j >= 0 && arr[j] > currVal; j--) {
                arr[j+1] = arr[j]
                arr[j] = currVal
        }
    }
    return arr;
}

 

굳이 새로운 배열을 위해 변수를 선언하지 않고 기존 배열을 정렬하는 방법도 있다.

 

0번째 요소를 정렬된 배열로 정하고, 이후 1번째 요소부터 정렬된 배열에 추가하면서 정렬한다.

currVal값이 정렬된 배열 마지막 요소 보다 크면 swap 하지 않고 중첩 반복문이 스킵된다.

 

버블 정렬 vs 선택 정렬 vs 삽입 정렬

선택정렬은 시간 복잡도가 좋지 않다. 정렬을 이해하기는 쉽다는 장점이 있다.

버블 정렬과 삽입 정렬은 거의 정렬된 상황에서 시간 복잡도가 O(N)으로 작동하여 상황에 맞게 최적화 할 수 있다.

 

추가로 삽입 정렬은 기존 정렬을 유지하면서 새로운 데이터를 정렬할 때 사용하는 것이 유용하다.

 

참조

Udemy - Js 알고리즘 & 자료구조 강의