[알고리즘] 삽입 정렬에 대해 알아보자! (+Python 구현)

본 포스팅에서는 삽입 정렬(Insertion sort) 알고리즘에 대해 알아봅니다.

📚 목차

1.  삽입 정렬이란?
2.  삽입 정렬의 동작 과정
3.  삽입 정렬 구현(Python)
4.  삽입 정렬의 시간 복잡도

1.  삽입 정렬이란?

삽입 정렬은 정렬이 필요한 데이터를 찾고 적절한 위치에 삽입하며 정렬하는 알고리즘입니다. 삽입 정렬은 필요할 때만 데이터를 비교하고 삽입하기 때문에 데이터가 어느 정도 정렬되어 있을 때 더욱 효율적으로 동작합니다. 이러한 특징 덕분에 정렬 상태와 상관없이 모든 데이터를 일일이 비교하며 정렬하는 방식인 선택 정렬보다 일반적으로 효율적입니다.

[알고리즘] 선택 정렬에 대해 알아보자! (+Python 구현)

2.  삽입 정렬의 동작 과정

이제 삽입 정렬의 구체적인 동작 과정을 알아보도록 하겠습니다. 삽입 정렬은 데이터가 삽입되기 이전에 반드시 삽입되는 위치 앞 데이터들은 모두 정렬되어 있다고 가정합니다.

 

1️⃣ 맨 앞에 있는 데이터는 그 자체로 이미 정렬되어 있는 상태로 가정하기 때문에 두 번째로 앞에 있는 데이터가 삽입될 위치를 찾고 적절한 위치에 삽입합니다.

2️⃣ 세 번째로 앞에 있는 데이터가 삽입될 위치를 찾고 적절한 위치에 삽입합니다.

3️⃣ 위와 같은 방식으로 전체 데이터가 정렬이 완료될 때까지 데이터가 삽입될 위치를 찾고 적절한 위치에 삽입하는 과정을 반복합니다.

 

그림 1 과 같이 정렬 없이 정수 6개가 무작위로 배치되어 있을 때 삽입 정렬을 활용해서 오름차순으로 정렬해 보도록 하겠습니다. 편의상 삽입해야 할 데이터를 파란색으로, 정렬되어 있는 데이터는 회색으로 표현하겠습니다. 또한, 삽입하기에 적절한 위치를 파란색 화살표로, 삽입 가능한 위치는 회색 화살표로 표현하겠습니다.

그림 1. 정렬되지 않고 무작위로 나열된 1부터 6까지 6개의 정수

(1) 맨 앞에 있는 3은 이미 정렬되어 있는 상태로 간주하기 때문에 두 번째로 앞에 있는 데이터 1을 삽입할 위치를 찾습니다. 삽입 가능한 위치는 3을 기준으로 왼쪽 혹은 오른쪽입니다. 우리는 오름차순으로 정렬할 것이기 때문에 삽입할 위치는 3의 왼쪽입니다.

 

(2) 다음으로 6은 1과 3 각각의 좌측 또는 우측에 삽입이 가능하지만 1과 3 보다 크기 때문에 현재 위치에 그대로 둡니다.

(3) 2는 1, 3, 6 각각의 좌측 또는 우측에 삽입이 가능하지만 1 보다는 크고 3 보다는 작기 때문에 1과 3 사이에 삽입합니다.

(4) 4는 3보다 크고 6 보다 작기 때문에 3과 6 사이에 삽입합니다.

(5) 5는 4보다 크고 6 보다 작기 때문에 4와 6 사이에 삽입합니다.

(6) 6은 가장 큰 값으로 데이터 삽입 없이 현재 위치에 그대로 두면 정렬이 완료됩니다.

위와 같이 (N-1)번 적절한 위치에 데이터를 삽입하는 과정을 거치면 데이터 정렬이 완료되는 것을 알 수 있습니다. 삽입 정렬의 특징은 정렬 과정을 거친, 회색으로 표현한 값들은 모두 이미 오름차순으로 정렬이 완료된 상태라는 것입니다.  이러한 특징 덕분에 특정 데이터가 삽입될 적절한 위치를 찾기 위해 현재 위치에서 좌측으로 한 칸씩 이동하며 데이터의 값을 비교하는 과정 중에 삽입해야 할 데이터보다 작은 값의 데이터를 만나면 그 위치가 삽입할 위치가 됩니다.

 

예를 들어, 아래 그림을 참고하여 다시 (3) 단계에서 데이터가 삽입될 위치를 찾는 과정을 살펴보겠습니다. 숫자 2가 삽입할 위치를 찾기 위해 좌측으로 한 칸씩 이동하며 각 위치에 있는 데이터와 값을 비교하는 과정을 거칩니다. 그러던 중 숫자 1이 더욱 작은 값이기 때문에 좌측으로 이동하는 과정을 멈추고 그 자리에(숫자 1 뒤) 데이터를 삽입합니다.

 

3.  삽입 정렬 구현(Python)

arr = [3, 1, 6, 2, 4, 5]

n = len(arr)
# 삽입할 데이터 선택
for i in range(1, n):
    # 인덱스 i부터 맨 앞까지 한 칸씩 이동하며 데이터 비교
    for j in range(i, 0, -1):
        # 데이터 위치 찾기
        if arr[j-1] > arr[j]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
        # 삽입할 데이터 보다 작은 데이터를 만나면 그 자리에서 멈춤    
        else:
            break

print(arr)

앞서 살펴본 예시를 파이썬을 통해 구현한 소스코드는 위와 같습니다.

[1, 2, 3, 4, 5, 6]

위와 같이 6개의 정수가 오름차순으로 정렬되어 출력되는 것을 확인하실 수 있습니다.

4.  삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 빅오 표기법으로 간략하게 O(N^2) 으로 표기할 수 있습니다. 이는 위에서 삽입 정렬을 구현할 때 이중 반복문을 활용했기 때문에 시간 복잡도가 O(N^2) 라는 것을 직관적으로 이해할 수 있습니다. 선택 정렬의 시간 복잡도 역시 O(N^2) 라고 했습니다. 하지만 삽입 정렬은 데이터가 어느 정도 정렬되어 있는 상태라면 매우 빠르게 동작한다고 말씀드렸습니다. 최선의 경우에는 O(N) 의 시간 복잡도를 가집니다. 이처럼, 데이터가 거의 정렬되어 있을 때는 퀵 정렬(Quick sort) 등의 타 정렬 기법보다 삽입 정렬을 활용했을 때 더욱 빠르게 동작할 수 있습니다.

📚 참고할 만한 포스팅

1.  [알고리즘] 선택 정렬에 대해 알아보자! (+Python 구현)
2.  [알고리즘] 삽입 정렬에 대해 알아보자! (+Python 구현)
3.  [알고리즘] 퀵 정렬에 대해 알아보자! (+Python 구현)
4.  [알고리즘] 계수 정렬에 대해 알아보자! (+Python 구현)
5.  [파이썬] 내장 함수를 활용한 데이터 정렬하기! (sorted, sort 함수)

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.