C++ 삽입 정렬의 시간 복잡도 완벽 정리

삽입 정렬의 시간 복잡도란?

시간 복잡도(time complexity)란 코드나 알고리즘이 입력 크기에 따라 실행 또는 처리되는 데 걸리는 시간을 의미합니다. 입력 데이터의 양이 늘어날수록 알고리즘의 실행 시간이 어떻게 변화하는지 나타내는 핵심 지표입니다.

삽입 정렬(insertion sort)의 시간 복잡도는 다음과 같습니다.

• 최선의 경우(Best case): O(n) — 이미 정렬된 배열이 입력으로 주어진 경우, 각 요소는 단 한 번의 비교만으로 제자리를 찾으므로 선형 시간에 정렬이 완료됩니다.
• 평균 및 최악의 경우(Average/Worst case): O(n²) — 배열이 무작위로 섞여 있거나 역순으로 정렬된 경우, 각 요소를 앞쪽의 정렬된 부분과 반복적으로 비교하고 이동시켜야 하므로 이차 시간이 소요됩니다.

특정 패턴의 배열에서 삽입 정렬의 시간 복잡도

다음과 같은 형태의 n 크기 배열에 삽입 정렬 알고리즘을 적용하면 시간 복잡도는 어떻게 될까요?

6, 5, 8, 7, 10, 9 … i, i-1

이 배열의 시간 복잡도는 O(n)입니다. 배열을 자세히 살펴보면 인접한 두 요소끼리 서로 위치가 바뀌어 있는 패턴을 확인할 수 있습니다. 즉, 첫 번째와 두 번째 요소가 교환되어 있고, 세 번째와 네 번째 요소가 교환되어 있으며, 이러한 규칙이 배열 전체에 걸쳐 반복됩니다. 각 요소는 올바른 위치에서 단 한 칸만 벗어나 있으므로, 정렬 과정에서 요소 하나당 상수 번의 연산만 필요합니다. 결과적으로 알고리즘은 한 번의 연산을 n번 수행하게 되며, 전체 시간 복잡도는 O(n)이 됩니다.

삽입 정렬의 정의와 C++ 구현 코드

삽입 정렬은 각 요소를 이미 정렬된 부분 배열 안에서 자신의 올바른 위치에 삽입하는 방식으로 데이터 구조를 정렬하는 알고리즘입니다. 마치 카드 게임에서 새로 받은 카드를 손에 든 정렬된 카드 사이의 적절한 자리에 끼워 넣는 것과 같은 원리입니다.

아래 코드는 삽입 정렬 함수를 구현한 예입니다 −

예제

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

코드 동작 설명

• 두 번째 요소(i = 1)부터 시작하여 현재 요소를 element 변수에 저장합니다.
• while 루프에서 현재 요소보다 큰 앞쪽 요소들을 한 칸씩 뒤로 이동시킵니다.
• 올바른 삽입 위치를 찾으면 현재 요소를 해당 위치에 배치합니다.
• 이 과정을 배열의 끝까지 반복하면 전체 배열이 오름차순으로 정렬됩니다.