삽입 정렬(Insertion Sort) 알고리즘

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

삽입 정렬(Insertion Sort)?

기준 좌표를 정하고 이전 좌표들의 원소 값과 비교하여 정렬 규칙에 맞으면 다음 좌표로 기준 좌표를 넘기고 정렬 규칙에 맞지 않으면 해당 좌표의 원소와 자리를 바꾼다.

삽입 정렬 동작

위 그림의 배열을 정렬한다고 해보자.

위 그림처럼 오름차순 정렬이라고 할 때 기준 좌표를 설정한 뒤 이전 좌표값들에 대해 기준 좌표보다 크면 한칸씩 swap한다. swap을 진행하다가 더 작은 값이 나와 정렬규칙을 만족한다면 과정을 종료하고 다음 기준 좌표값을 설정하여 마저 진행한다. 최악의 경우를 상정한다면(역순 배열) 시간복잡도는 $O(n^2)$이 되지만 일반적으로 완전 탐색을 진행하는 버블 정렬이나 선택 정렬과 비교했을 때 중간에 정렬 규칙을 만족한다면 다음 단계로 진행하기 때문에 비교적 빠르다.

python 코드

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

a = [3, 1, 2, 5, 4, 6]
b = [6, 5, 4, 3, 2, 1]
c = [5, 5, 3, 3, 1, 1]
print(f'insertion a:{insertion(a)}, b:{insertion(b)}, c:{insertion(c)}')