삽입 정렬은 간단하지만 유용한 정렬 알고리즘입니다. 이 알고리즘은 두 부분으로 나눠지며, 하나는 정렬된 요소들이고 다른 하나는 정렬되지 않은 요소들입니다. 정렬되지 않은 부분의 요소를 하나씩 골라 정렬된 부분의 올바른 위치에 삽입하여 정렬하는 방식으로 동작합니다.

알고리즘 동작 방식

1. 첫 번째 요소를 정렬된 부분으로 취급합니다.
2. 정렬되지 않은 부분의 다음 요소를 정렬된 부분에 올바른 위치에 삽입할 때까지 반복합니다.
3. 모든 요소가 정렬될 때까지 2번을 반복합니다.

예시 코드

public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

위의 코드는 Java로 삽입 정렬을 구현한 예시입니다.

시간 복잡도

삽입 정렬의 평균 및 최악의 시간 복잡도는 O(n^2)입니다. 최선의 경우에는 이미 정렬된 배열에 대해서 O(n)의 시간 복잡도를 갖습니다.

마치며

삽입 정렬은 구현이 간단하고 작은 배열에 대해서는 효율적인 정렬 알고리즘입니다. 그러나 큰 배열에 대해서는 다른 고급 정렬 알고리즘보다 성능이 떨어지므로 주의해야 합니다.

참고 문헌: GeeksforGeeks - Insertion Sort