Unity 개발자를 위한 C# Insertion Sort(삽입 정렬) 구현

Insertion Sort(삽입 정렬)는 정렬된 구간에 새로운 값을 알맞은 위치에 “삽입”하면서 정렬을 진행하는 방식입니다.

 

Selection Sort가 “현재 구간 전체에서 최솟값을 선택해 한 번 교환”하는 방식이라면, Insertion Sort는 “이미 정렬된 구간 내부에서 위치를 찾아 값을 밀어내며 삽입”합니다. 두 알고리즘 모두 비교 기반 정렬이지만, 비교가 발생하는 위치와 데이터 이동 방식이 완전히 다릅니다.

 

Insertion Sort는 특히 데이터 이동이 ‘교환(swap)’이 아니라 ‘이동(shift)’ 중심이라는 점에서, 비교/교환 관점으로 비용을 분해해 이해하기에 좋은 알고리즘입니다.

---

1. Insertion Sort의 구조와 동작 방식

1.1 기본 아이디어

Insertion Sort는 배열의 앞부분을 항상 정렬된 구간으로 유지합니다. 초기에는 첫 번째 원소 하나만으로도 “정렬된 상태”라고 가정합니다.

정렬되지 않은 다음 원소 하나를 꺼내, 이미 정렬된 구간 내부에서 들어갈 위치를 찾고, 그 위치에 값을 삽입합니다.

• [0 .. i-1] 구간은 항상 정렬되어 있다.
• i 위치의 값을 꺼내(key)
• 정렬된 구간 안에서 알맞은 위치를 찾아 삽입

1.2 Pass 단위 동작

Pass i는 “i번째 값을 정렬된 구간 [0..i-1] 안에 삽입”하는 단계입니다.

• 시작 시점: [0..i-1]은 정렬됨
• key = array[i]를 임시 저장
• 뒤에서부터 비교하며 큰 값들을 한 칸씩 오른쪽으로 이동
• 빈 자리에 key를 삽입

한 Pass가 끝나면 [0..i] 구간 전체가 정렬됩니다.

 

※ 동작을 시각적으로 확인해보기

아래 링크는 Insertion Sort의 정렬된 구간(sorted prefix)을 유지하면서, 새로운 원소를 알맞은 위치에 삽입하기 위해 기존 원소들을 한 칸씩 이동(shift)시키는 과정을 단계별로 시각화해 주는 도구입니다. 각 단계에서 “비교 → 이동 → 삽입” 흐름이 어떻게 반복되는지 확인할 수 있습니다.

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

---

2. 왜 O(N²)이 되는가 (비교 흐름 기준)

Insertion Sort의 핵심 비용은 삽입 위치를 찾기 위한 비교와 그 과정에서 발생하는 이동(shift)입니다.

• Pass 1: 최대 1번 비교
• Pass 2: 최대 2번 비교
• ...
• Pass N-1: 최대 (N-1)번 비교

최악의 경우(역순 정렬) 비교 횟수는 다음과 같이 누적됩니다.

(1) + (2) + ... + (N - 1)
= N(N - 1) / 2

이 누적 비교 구조 때문에 최악 시간 복잡도는 O(N²)입니다.

 

다만 Insertion Sort는 입력 상태에 따라 비교 횟수와 이동 횟수가 크게 달라질 수 있습니다.

• 이미 정렬된 경우: 조건 비교 후 바로 종료되며 이동은 발생하지 않음
• 거의 정렬된 경우: 매우 빠르게 종료

---

3. Insertion Sort의 특징과 한계

1) 데이터 이동이 많음 (Swap이 아닌 Shift)

Insertion Sort는 값을 교환(swap)하지 않고, 여러 값을 한 칸씩 밀어내는 방식(shift)을 사용합니다.

따라서 데이터 이동 비용이 큰 경우에는 Selection Sort보다 불리할 수 있습니다.

 

2) 이미 정렬된 경우 매우 효율적

Insertion Sort는 이미 정렬된 상태에서는 각 Pass마다 비교 1회만 수행하고 바로 종료됩니다.

즉, 입력 상태에 따라 성능 편차가 큰 알고리즘입니다.

 

3) 안정 정렬(Stable Sort)

Insertion Sort는 값을 뒤에서 앞으로 이동시키면서 삽입하되, 같은 키를 가진 원소의 상대 순서를 유지합니다. 따라서 Insertion Sort는 안정 정렬(Stable Sort)입니다.

---

4. 실행 흐름을 예제로 확인하기

예제 배열: [64, 25, 12, 22, 11]
정렬 기준: 오름차순

 

4.1 j는 무엇이고, 어떻게 변하는가?

Insertion Sort에서 j는 현재 삽입 대상(key)과 비교할 정렬된 구간의 인덱스를 의미합니다.

각 Pass에서 i번째 값을 삽입할 때, 이미 정렬되어 있는 구간은 [0..i-1]이며, j는 이 구간의 오른쪽 끝(i-1)에서 시작합니다.

• i : 이번 Pass에서 삽입할 대상의 인덱스
• key : 삽입할 실제 값 (array[i])
• j : key와 비교하며 왼쪽으로 이동하는 탐색 포인터

Insertion Sort는 다음 조건이 만족되는 동안 j를 감소시키며 반복합니다.

while (j >= 0 && array[j] > key)

이 조건은 다음 의미를 가집니다.

• j >= 0 : 정렬된 구간의 왼쪽 경계를 넘지 않도록 제한
• array[j] > key : key보다 큰 값만 오른쪽으로 이동

조건이 참인 동안에는 array[j]를 array[j+1]로 이동시키고, j를 1 감소시켜 왼쪽으로 한 칸 이동합니다.

 

반복이 종료되는 시점은 다음 두 가지 중 하나입니다.

• j == -1 : key가 정렬된 구간의 맨 앞에 삽입되어야 하는 경우
• array[j] <= key : key보다 작거나 같은 값을 만난 경우

따라서 key가 최종적으로 삽입될 위치는 항상 j + 1이 됩니다.

 

4.2 Pass별 실행 흐름

Pass 1 (i = 1)

현재 삽입 대상은 array[1] = 25입니다.
정렬된 구간은 [0..0]이며, 값은 [64]입니다.

• key = 25
• j = 0
• array[0] = 64 > key(25) → 한 칸 오른쪽으로 이동

이동 결과: [64, 64, 12, 22, 11]

j가 -1이 되어 반복 종료

삽입 위치: j + 1 = 0
결과 배열: [25, 64, 12, 22, 11]

[0..1] 구간이 정렬되었습니다.

 

Pass 2 (i = 2)

현재 삽입 대상은 array[2] = 12입니다.
정렬된 구간은 [0..1]이며, 값은 [25, 64]입니다.

• key = 12
• j = 1 → array[1] = 64 > 12 → 이동
• j = 0 → array[0] = 25 > 12 → 이동

이동 결과: [25, 25, 64, 22, 11]
j가 -1이 되어 반복 종료

삽입 위치: j + 1 = 0
결과 배열: [12, 25, 64, 22, 11]

[0..2] 구간이 정렬되었습니다.

 

Pass 3 (i = 3)

현재 삽입 대상은 array[3] = 22입니다.
정렬된 구간은 [0..2]이며, 값은 [12, 25, 64]입니다.

• key = 22
• j = 2 → 64 > 22 → 이동
• j = 1 → 25 > 22 → 이동
• j = 0 → 12 <= 22 → 비교 종료

삽입 위치: j + 1 = 1
결과 배열: [12, 22, 25, 64, 11]

[0..3] 구간이 정렬되었습니다.

 

Pass 4 (i = 4)

현재 삽입 대상은 array[4] = 11입니다.
정렬된 구간은 [0..3]이며, 값은 [12, 22, 25, 64]입니다.

• key = 11
• j = 3 → 64 > 11 → 이동
• j = 2 → 25 > 11 → 이동
• j = 1 → 22 > 11 → 이동
• j = 0 → 12 > 11 → 이동

모든 값이 이동된 후 j = -1

삽입 위치: j + 1 = 0
결과 배열: [11, 12, 22, 25, 64]

전체 배열이 정렬되었습니다.

• 각 Pass는 “key 선택 → j 감소 → 조건 비교 → 이동 → 삽입” 구조
• 정렬된 구간이 왼쪽에서 오른쪽으로 1칸씩 확장됨

---

5. C# 기반 Insertion Sort 직접 구현 코드

using System;

namespace Daebak.Common.Algorithms.Sorting
{
    public static class InsertionSort
    {
        public static void Sort(int[] array)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            int n = array.Length;
            if (n <= 1)
            {
                return;
            }

            // i는 "삽입할 대상"의 인덱스
            for (int i = 1; i < n; i++)
            {
                // 현재 삽입할 값을 임시 저장
                int key = array[i];

                // 정렬된 구간의 마지막 인덱스
                int j = i - 1;

                // key보다 큰 값들을 한 칸씩 뒤로 이동
                while (j >= 0 && array[j] > key)
                {
                    array[j + 1] = array[j];
                    j--;
                }

                // 비어 있는 위치에 key 삽입
                array[j + 1] = key;
            }
        }
    }
}

이 코드에서 구조적으로 중요한 포인트는 다음과 같습니다.

• 삽입 대상(key)은 미리 저장하여 덮어쓰기를 방지
• 비교는 정렬된 구간 내부에서만 발생
• 교환이 아닌 이동(shift) 중심 구조

---

6. Unity 환경에서 테스트 해보기

using UnityEngine;
using Daebak.Common.Algorithms.Sorting;

public class Test_InsertionSort : MonoBehaviour
{
    private void Start()
    {
        int[] data = new int[] { 64, 25, 12, 22, 11 };

        Debug.Log("Before Sort : " + string.Join(", ", data));

        InsertionSort.Sort(data);

        Debug.Log("After Sort  : " + string.Join(", ", data));
    }
}

 

출력 결과

Before Sort : 64, 25, 12, 22, 11
After Sort : 11, 12, 22, 25, 64

---

7. 마무리

Insertion Sort는 “정렬된 구간에 값을 삽입한다”는 직관적인 구조를 가진 정렬입니다.

• 비교: 입력 상태에 따라 크게 달라짐
• 이동: swap이 아닌 shift 중심
• 안정성: Stable Sort

Selection Sort가 “비교는 많지만 교환은 제한된 구조”라면, Insertion Sort는 “이동이 많은 대신 입력 상태에 민감한 구조”입니다.

이 두 알고리즘을 비교/교환/이동 관점에서 정리해두면, 이후 Merge Sort, Quick Sort를 이해할 때 정렬 비용 구조를 훨씬 선명하게 볼 수 있습니다.

 

※ 다음 글에서는 Shell Sort를 살펴보며, Insertion Sort를 기반으로 간격(gap)을 두고 데이터를 미리 이동시켜 전체 이동 비용을 줄이는 아이디어가 어떻게 성능 개선으로 이어지는지를 정리합니다.