정렬 알고리즘의 기초 3편 : 삽입 정렬 (Insertion Sort)

이번 글에서는 정렬 알고리즘 시리즈의 마지막으로 삽입 정렬을 다룹니다.
삽입 정렬은 정렬된 구간에 새로운 값을 적절한 위치에 삽입하는 방식으로 동작하며, 간단한 구현에도 불구하고 실제로 사용하는 경우가 종종 있을 정도로 효율적인 경우도 있습니다.

 

삽입 정렬이란?

삽입 정렬은 배열의 두 번째 요소부터 시작하여, 왼쪽에 있는 정렬된 부분과 비교하면서 적절한 위치를 찾아 값을 끼워 넣는 방식입니다. 이러한 정렬 방식은 우리가 카드 놀이에서 손에 들고 하나씩 정렬하는 방식과 유사합니다.

 

작동 방식 요약

1. 두 번째 요소부터 시작합니다.

2. 현재 값을 왼쪽의 정렬된 구간과 비교합니다.

3. 더 큰 값이 있다면 오른쪽으로 한 칸씩 밀어냅니다.

4. 비어 있는 자리에 현재 값을 삽입합니다.

5. 배열 끝까지 반복하면 정렬이 완료됩니다.

 

C# 코드 예시

int[] numbers = { 52, 86, 3, 79, 45, 12, 99, 23, 56, 78 };

for (int i = 1; i < numbers.Length; i++)
{
    int key = numbers[i];
    int j = i - 1;

    while (j >= 0 && numbers[j] > key)
    {
        numbers[j + 1] = numbers[j];
        j--;
    }

    numbers[j + 1] = key;
}

Console.WriteLine(string.Join(", ", numbers));

 

이 코드는 key 에 현재 값을 저장한 뒤, 왼쪽 값들과 비교하면서 더 큰 값은 오른쪽으로 한 칸씩 밀어낸 후, key 값을 적절한 위치에 삽입합니다.

 

삽입 정렬이라는 이름의 유래

삽입 정렬은 말 그대로 값을 정렬된 구간에 '삽입' 하는 방식으로 정렬이 이루어집니다.
이처럼 하나씩 자리를 찾아 들어가는 동작 방식 때문에 삽입 정렬(Insertion Sort) 이라는 이름이 붙었습니다.

 

마무리

삽입 정렬은 단순하면서도 효율적인 알고리즘으로, 특히 이미 정렬된 데이터가 많은 경우 빠르게 동작하는 장점이 있습니다. 버블, 선택, 삽입 정렬 모두 시간 복잡도는 O(n²) 이지만, 삽입 정렬은 최선의 경우 O(n) 으로 작동할 수 있어 실용적인 면도 갖추고 있습니다. 

이제 세 가지 정렬 알고리즘의 기초를 모두 살펴보았습니다.
이해가 잘 되셨다면, 다음 단계로 퀵 정렬, 병합 정렬 등 고급 정렬 알고리즘으로 넘어가보셔도 좋습니다.