삽입 정렬(Insertion Sort)

wisdom·2022년 8월 27일

삽입 정렬은 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

손으로 카드를 정렬하는 방법과 유사하다.

1. 알고리즘

리스트의 첫 번째 위치의 값은 이미 정렬이 완료된 리스트다.
정렬 리스트의 오른쪽에 있는 정렬되지 않은 원소를 왼쪽으로 이동하면서 원소들과 비교하여 삽입한다.
이 과정을 정렬되지 않은 원소가 없을 때까지 반복한다.

2. 구현 (오름차순)

Java

void insertionSort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) { // 두 번째 원소부터 탐색한다.
        int key = arr[i];
        int j = i - 1;

        // key보다 큰 원소를 한 위치씩 뒤로 보낸다.
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // 삽입
        arr[j + 1] = key;
    }
}

3. 시간복잡도

Worst Case (반대로 정렬된 경우) : $O(n^2)$
Average Case : $O(n^2)$
Best Case (이미 정렬된 경우) : $O(n)$

4. 공간복잡도

in-place 알고리즘으로, 추가적인 자료구조를 사용하지 않는다.

Auxiliary Space (보조 공간) : $O(1)$

5. 장점

알고리즘이 단순하다.
대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. (in-place sorting)
안정 정렬(Stable Sort)이다.
Selection Sort나 Bubble Sort과 같은 $O(n^2)$ 알고리즘에 비교하여 상대적으로 빠르다.

6. 단점

평균과 최악의 시간복잡도가 $O(n^2)$ 으로 비효율적이다.
Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.

🔖 참고

wisdom

백엔드 개발자

이전 포스트

선택 정렬(Selection Sort)

다음 포스트