[파이썬 알고리즘] 정렬 알고리즘 (3) - 삽입 정렬

이번 시간에는 정렬 알고리즘 시리즈의 세 번째로 삽입 정렬(Insertion Sort)에 대해 알아보겠습니다.

 

삽입 정렬은 우리가 카드 게임에서 손에 카드를 한 장씩 정리해 나가는 방식과 매우 유사한 정렬 알고리즘입니다.

---

1. 삽입 정렬

삽입 정렬은 위 문제를 풀 때 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결합니다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 ‘필요할 때만’ 위치를 바꾸게 됩니다.

즉, 각 숫자를 적절한 위치에 삽입하면 어떨까?

 

동작 방식

• 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.
• 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾습니다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킵니다.
• 처음 Key값은 두 번째 자료부터 시작한다.

구체적인 알고리즘 방법은 아래 그림을 통해 확인할 수 있습니다.

 

 

---

2. 파이썬 구현 코드

def insertion_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            else:
                break

    return arr

 

시간 복잡도

 

• 최선의 경우, 내부 반복문이 break에 의해 빠르게 끝나므로 O(n)
• 최악의 경우, 모든 원소를 계속 뒤로 밀어야 하므로 O(n²)
• 하지만 데이터가 거의 정렬된 상태일수록 효율이 좋음

삽입 정렬의 장단점

✅ 장점

• 구현이 쉽고 직관적
• 거의 정렬된 배열에서는 매우 빠름
• 제자리 정렬 (in-place) → 추가 메모리 필요 없음

❌ 단점

• 평균/최악 시간복잡도 O(n²)
• 큰 배열에서는 비효율적

---

마무리

삽입 정렬은 성능 측면에서 다른 고급 정렬 알고리즘(퀵 정렬, 병합 정렬 등)에 비해 느리지만,

간단한 구현과 안정성, 정렬된 데이터에 대한 효율성 덕분에 알고리즘 입문자에게는 좋은 연습 대상입니다.

 

특히, 정렬이 거의 되어 있는 배열을 다룰 때 매우 유용하므로, 특정 상황에서는 충분히 실용적인 알고리즘입니다.

 

읽어주셔서 감사합니다.

 

References

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog