파이썬으로 구현하는 삽입 정렬(Insertion Sort) 완벽 가이드

이 글에서는 Python 3.x 이상 버전에서 삽입 정렬(Insertion Sort)을 구현하는 방법에 대해 알아보겠습니다.

알고리즘 동작 원리

삽입 정렬은 다음과 같은 단계로 동작합니다.

1. 각 반복마다 정렬된 배열의 범위를 하나씩 넓혀가며 입력 요소를 순회합니다.
2. 현재 요소(key)를 정렬된 배열에서 가장 큰 값과 비교합니다.
3. 현재 요소가 더 크다면 그 자리에 그대로 두고 다음 요소로 넘어갑니다.
   그렇지 않다면 정렬된 배열 내에서 올바른 위치를 찾아 그곳으로 이동시킵니다.
4. 이 과정은 정렬된 배열에서 현재 요소보다 큰 모든 요소들을
   한 칸씩 오른쪽으로 밀어냄으로써 수행됩니다.

이제 알고리즘의 시각적인 동작 과정을 살펴보겠습니다.

구현 예제

다음은 위 알고리즘을 파이썬 코드로 구현한 예제입니다.

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i]
      # arr[0..i-1] 범위에서 key보다 큰 요소들을
      # 현재 위치에서 한 칸 뒤로 이동시킵니다
      j = i-1
      while j >= 0 and key < arr[j]:
         arr[j+1] = arr[j]
         j -= 1
      arr[j+1] = key
# 메인 부분
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print("정렬된 배열:")
for i in range(len(arr)):
   print(arr[i])

실행 결과

위 코드를 실행하면 문자들이 알파벳 순서대로 정렬되어 출력됩니다.

정렬된 배열:
a
i
l
o
r
t
t
u

복잡도 분석

시간 복잡도 − O(n²) : 최악의 경우 모든 요소 쌍을 비교해야 하므로 이차 시간이 소요됩니다.

보조 공간(공간 복잡도) − O(1) : 추가적인 배열 없이 제자리(in-place)에서 정렬이 수행됩니다.

참고로, 모든 변수는 아래 그림과 같이 전역 프레임(global frame)에 선언되어 관리됩니다.

결론

이번 글에서는 삽입 정렬의 개념과 Python 3.x 이상 버전에서의 구현 방법을 살펴보았습니다. 삽입 정렬은 구현이 간단하고, 데이터 양이 적거나 이미 거의 정렬된 배열에서는 매우 효율적으로 동작하기 때문에 정렬 알고리즘의 기초를 익히기에 좋은 예제입니다. 실무에서는 대용량 데이터에 대해 퀵 정렬이나 병합 정렬 같은 고급 알고리즘을 사용하지만, 삽입 정렬의 동작 원리를 이해하면 다른 정렬 알고리즘을 학습하는 데 큰 도움이 됩니다.