삽입 정렬(Insertion Sort)

개념

삽입 정렬은 특정 원소의 앞에 있는 원소들이 이미 정렬되어 있다는 가정 하에 앞에 원소에서 적절한 위치에 특정 원소를 삽입하는 정렬 방식이다. 

예제를 살펴보면서 삽입 정렬이 어떻게 수행되는지 살펴보자.

 

예제

다음 숫자들을 오름차순으로 정렬하라.

삽입정렬에서는 앞에 있는 원소들이 정렬되어 있는 것을 가정하기 때문에 자신보다 작은 수(오름차순 시 우선순위가 높은 원소)를 만나면 바로 그 뒤가 삽입되어야 할 위치이고, 그 전까지는 큰 수를 만나면 하나씩 자신보다 뒤로 밀어낸다고 생각하면 된다.

10 앞에는 삽입할 위치가 없으니 3부터 시작해보자. 3 앞에 있는 원소들이 정렬되어 있다는 가정하에 3 은 어디에 삽입되어야 할까?
인접한 원소부터 앞으로 차례차례 비교해보면 10은 3보다 크고, 그 앞에는 비교할 대상이 존재하지 않으므로 10이 있는 위치에 3을 삽입한다.

그 다음 4를 살펴보자. 4 또한 앞에 있는 원소들이 이미 정렬되어 있다고 할 때 인접한 수부터 차례로 비교를 해보자. 
바로 앞에 있는 10은 4보다 크므로 일단 4는 10보다는 앞에 있어야 한다.
이제 그 다음에 있는 3을 살펴보자. 3은 4보다는 작으므로 4는 3 뒤에 삽입되어야 한다. 

 

이처럼 삽입정렬은 특정 원소를 기준으로 앞에 원소를 계속 비교해가며, 자기 자신보다 작은 수가 나올 때까지 찾아서 그 뒤에 삽입하는 과정을 반복해나가며 정렬을 수행하며 결국 이렇게 오름차순 정렬이 완료된다.

이제 이를 자바 코드로 구현해보자.

import java.util.Arrays;

public class AscendingSort {
    public static void insertionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int j = i;
            while (j >= 0 && array[j] > array[j + 1]) {
                swap(j, j + 1, array);
                j--;
            }
        }
    }

    private static void swap(int a, int b, int[] array) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
        return;
    }

    public static void main(String[] args) {
        int[] array = {10, 3, 4, 1, 6, 8, 9, 5, 2, 7};
        insertionSort(array);
        System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}

시간복잡도

삽입 정렬은 기본적으로 버블정렬, 선택정렬과 같이 O(N^2)의 시간복잡도를 가진다.

하지만 특정 원소를 기준으로 앞에 있는 원소는 모두 정렬이 되어 있다는 기준으로 정렬하기 때문에 정렬이 거의 되어 있는 경우에는 어떤 알고리즘 보다 빠르다는 특성을 갖고 있다.