파이썬 삽입 정렬(Insertion Sort)이란? 개념부터 코드 구현까지 총정리

삽입 정렬(Insertion Sort)은 배열을 정렬하는 가장 간단하고 직관적인 알고리즘 중 하나입니다. 이 기법에서는 배열을 개념적으로 정렬된 부분과 정렬되지 않은 부분으로 나누어 생각합니다. 그 후 정렬되지 않은 부분에서 요소를 하나씩 꺼내어, 정렬된 부분 안에서 올바른 위치를 찾아 삽입하는 방식으로 정렬을 진행합니다.

삽입 정렬의 동작 원리

• 배열의 요소를 인덱스 1부터 n까지 순서대로 순회합니다.

• 현재 위치 i의 요소가 바로 앞의 요소보다 크다면, 이미 올바른 자리에 있는 것이므로 이동할 필요가 없습니다.

• 현재 위치 i의 요소가 바로 앞의 요소보다 작다면, 자신보다 작은 요소를 만나거나 배열의 가장 왼쪽 끝(인덱스 0)에 도달할 때까지 계속 왼쪽으로 이동시킵니다.

예제로 이해하기

구체적인 예시를 통해 삽입 정렬의 동작 과정을 살펴보겠습니다. 다음과 같은 배열이 있다고 가정해 보겠습니다.

순회는 인덱스 1부터 시작합니다. 인덱스 0에는 비교할 선행 요소가 없기 때문입니다.

인덱스 1

6은 선행 요소인 4보다 크므로, 아무 작업도 필요하지 않습니다.

인덱스 2

1은 선행 요소보다 작으므로, 자신보다 작은 요소를 만나거나 인덱스 0에 도달할 때까지 왼쪽으로 이동시킵니다. 이 경우 인덱스 0까지 이동하게 됩니다.

인덱스 3

7은 선행 요소인 6보다 크므로, 이동할 필요가 없습니다.

인덱스 4

2를 자신보다 작은 요소(1)를 만날 때까지 왼쪽으로 이동시킵니다.

인덱스 5

5를 자신보다 작은 요소(4)를 만날 때까지 왼쪽으로 이동시킵니다.

이렇게 하여 최종적으로 정렬된 배열을 얻을 수 있습니다.

시간 복잡도와 공간 복잡도

삽입 정렬은 제자리(in-place) 정렬 알고리즘으로, 추가 메모리가 거의 필요하지 않습니다. 시간 복잡도는 O(n²), 공간 복잡도는 O(1)입니다. 데이터 양이 적거나 대부분 정렬된 상태에 가까운 배열에서는 효율적으로 동작한다는 장점이 있습니다.

파이썬 구현 코드

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 각 요소를 하나씩 가져옴
        j = i - 1
        # 인덱스 0에 도달하거나 key보다 작은 요소를 만날 때까지 계속 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

arr = [4, 6, 1, 7, 2, 5]
insertionSort(arr)
for i in range(len(arr)):
    print(arr[i], end=" ")

실행 결과

1 2 4 5 6 7