[알고리즘] 삽입 정렬 (Insertion Sort) 완전 정리

 

1. 삽입 정렬이란?

 

삽입 정렬(Insertion Sort)은 정렬되지 않은 데이터를 하나씩 꺼내어, 정렬된 부분에 ‘삽입’해나가는 방식의 정렬 알고리즘이다.

 

쉽게 말하면, 앞에서부터 차례대로 정렬을 만들어나가는 방식이다.

각 단계에서 현재 값을 앞쪽 정렬된 부분에 적절한 위치에 끼워 넣으며 진행한다.

 

---

2. 삽입 정렬의 동작 원리

 

초기 배열이 다음과 같다고 가정하자.

[7, 3, 5, 1]

삽입 정렬의 흐름은 다음과 같다.

 

1. 7은 첫 번째 원소이므로 그대로 두고 시작
2. 3은 7보다 작으므로 앞으로 삽입 → [3, 7, 5, 1]
3. 5는 7보다 작고 3보다 크므로, 7을 뒤로 밀고 중간에 삽입 → [3, 5, 7, 1]
4. 1은 모두보다 작으므로 전부 밀고 맨 앞으로 삽입 → [1, 3, 5, 7]

 

정렬이 완료된 최종 배열: [1, 3, 5, 7]

 

---

3. 삽입 정렬의 특징

항목설명

항목	설명
정렬 방식	앞에서부터 차례로 정렬된 부분에 삽입
정렬 안정성	안정 정렬 (같은 값의 순서가 유지됨)
공간 복잡도	O(1) (추가 메모리 없음)
시간 복잡도 (평균/최악)	O(N²)
시간 복잡도 (최선: 이미 정렬된 경우)	O(N)
주요 특징	구현이 간단하고, 데이터 수가 적을 때 유리

 

---

4. 삽입 정렬 코드 (Java)

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        // 앞쪽 정렬된 배열에서 key보다 큰 값은 뒤로 밀기
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 삽입할 위치에 key 넣기
        arr[j + 1] = key;
    }
}

---

5. 삽입 정렬이 적합한 상황

 

• 데이터의 수가 적고 정렬 비용이 크지 않은 경우
• 거의 정렬된 데이터에 대해 빠른 성능이 필요한 경우
• 정렬 과정 중 이동 횟수, 삽입 위치를 추적해야 하는 문제

---

6. 코딩 테스트에서 삽입 정렬을 떠올릴 수 있는 단서

 

• 앞에서부터 차례로 정렬해 나간다
• 자신보다 큰 데이터를 뒤로 미룬다
• 정렬 과정 자체에서의 이동 횟수를 구한다
• 중간에 값을 삽입하거나 끼워 넣는 로직이 필요하다

 

이런 표현이 문제에 있다면, 삽입 정렬을 의심해볼 수 있다.

 

---

7. 마무리

 

삽입 정렬은 알고리즘 중 가장 기초적이면서도,

정렬의 “원리”와 “흐름”을 이해하기에 가장 적합한 알고리즘이다.

 

단순히 외워서 쓰기보다는,

“앞에 있는 값들과 비교하면서 밀고, 자리를 찾아 넣는다”는 아이디어를 이해해두면,

다양한 문제에서 유연하게 적용할 수 있다.

 

코딩 테스트에서는 단순 구현형 문제나

“몇 번 밀었는지”, “정렬이 어떻게 이루어지는지”를 묻는 문제에서 특히 유용하게 쓰인다.