JavaScript 삽입 정렬(Insertion Sort)로 숫자 배열 오름차순 정렬하기

문제 소개

숫자 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 삽입 정렬(Insertion Sort) 알고리즘을 활용하여 배열의 요소들을 오름차순으로 정렬해야 합니다.

삽입 정렬은 마치 카드 게임에서 손에 든 카드를 정렬하듯이, 각 요소를 이미 정렬된 앞부분의 적절한 위치에 하나씩 삽입해 나가는 방식의 정렬 알고리즘입니다. 구현이 간단하고 데이터 양이 적거나 거의 정렬된 배열에서 효율적으로 동작한다는 장점이 있습니다.

예를 들어 함수의 입력이 다음과 같다면,

입력

const arr = [5, 8, 1, 3, 9, 4, 2, 7, 6];

출력

const output = [1, 2, 3, 4, 5, 6, 7, 8, 9];

구현 코드

다음은 삽입 정렬을 구현한 전체 코드입니다.

const arr = [5, 8, 1, 3, 9, 4, 2, 7, 6];

const insertionSort = (arr = []) => {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        // 현재 정렬할 값을 임시 저장
        let curr = arr[i];
        let j = i - 1;

        // 현재 값보다 큰 요소들을 한 칸씩 뒤로 이동
        while ((j > -1) && (curr < arr[j])) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 올바른 위치에 현재 값 삽입
        arr[j + 1] = curr;
    };
    return arr;
}

console.log(insertionSort(arr));

출력 결과

[1, 2, 3, 4, 5, 6, 7, 8, 9]

코드 동작 원리

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1. 인덱스 1부터 시작하는 이유는 첫 번째 요소 하나만으로는 이미 '정렬된 상태'라고 볼 수 있기 때문입니다.
2. 반복문이 진행될 때마다 현재 위치의 값을 curr 변수에 임시로 저장합니다.
3. 내부 while 반복문은 왼쪽에 있는 요소들이 현재 값보다 클 동안 해당 요소들을 한 칸씩 오른쪽으로 밀어냅니다.
4. 더 이상 밀어낼 요소가 없으면, 비워진 자리에 curr 값을 삽입합니다.
5. 모든 요소에 대해 위 과정을 반복하면 배열 전체가 오름차순으로 정렬됩니다.

시간 복잡도

삽입 정렬의 평균 및 최악의 경우 시간 복잡도는 O(n²)이며, 이미 정렬된 배열이 입력되는 최선의 경우에는 O(n)으로 매우 빠르게 동작합니다. 또한 제자리(in-place) 정렬 방식이므로 추가 메모리가 거의 필요 없고, 공간 복잡도는 O(1)입니다.