삽입 정렬 (Insertion Sort)

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘.
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
• 알고리즘의 과정
  • 처음의 탐색 시작 값은 두 번째 자료부터 시작한다.
  • 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정리.
  • 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째 자료와 첫 번째 자료, 네 번째 자료는 세 번째 자료와 두 번째, 첫 번째 자료, ... 이렇게 비교를 한 후 자료가 삽입될 위치를 찾는다
  • 자료의 삽입 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 다른 자료를 한 칸씩 뒤로 이동시킨다.

파이썬으로 코드 구현

 

코드 구현

def insertionsort(list):
    for i in range(1, len(list)): # 두 번째 자리부터 탐색을 시작
        for j in range(i, 0, -1): # 인덱스 i부터 1까지 역순으로 탐색 진행
            if list[j] < list[j - 1]:  # 현재 원소가 왼쪽의 원소보다 더 작은지 확인
                list[j], list[j - 1] = list[j - 1], list[j] # 정렬을 위해 더 작은 원소를 왼쪽으로 위치 교환
            else:  # 현재 원소가 왼쪽의 원소보다 크다면 다음 회차로 바로 진행
                break

 

알고리즘 테스트

test = [3, 0, 11, 8, 3, 16, 1, 8, 4, 7]
insertionsort(test)
print(test)

 

결과

[0, 1, 3, 3, 4, 7, 8, 8, 11, 16]

 

알고리즘 테스트 2

 

아래의 네가지 데이터를 넣고 테스트도 진행해 보았다.

1. 정렬이 끝난 배열
2. 역순으로 정렬된 배열
3. 원소가 전부 같은 배열
4. 랜덤으로 구성된 배열

import time

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

test1 = [1, 2, 3, 4, 5, 6, 7]
test2 = [7, 6, 5, 4, 3, 2, 1]
test3 = [1, 1, 1, 1, 1, 1, 1, 1]
test4 = [23, 15, 38, 94, 62, 123, 243, 234, 112]

start_time1 = time.time()
selectionsort(test1)
end_time1 = time.time()
total_time1 = (end_time1 - start_time1) * 100

start_time2 = time.time()
selectionsort(test2)
end_time2 = time.time()
total_time2 = (end_time2 - start_time2) * 1000

start_time3 = time.time()
selectionsort(test3)
end_time3 = time.time()
total_time3 = (end_time3 - start_time3) * 1000

start_time4 = time.time()
selectionsort(test4)
end_time4 = time.time()
total_time4 = (end_time4 - start_time4) * 1000

print(f'{total_time1:.4f}ms')
print(f'{total_time2:.4f}ms')
print(f'{total_time3:.4f}ms')
print(f'{total_time4:.4f}ms')

결과

0.0077ms
0.0372ms
0.0362ms
0.0370ms

 

random 데이터로 성능 테스트

import random
import time

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

data = [random.randint(1, 1000000) for _ in range(1000)]
start_time = time.time()
insertionsort(data)
print(data)
end_time = time.time()
total_time = end_time - start_time
print(f'{total_time:.4f}초')

• 데이터가 1000개 일 때 : 0.0271초
• 데이터가 2000개 일 때 : 0.1137초
• 데이터가 4000개 일 때 : 0.4614초
• 데이터가 5000개 일 때 : 0.7170초
• 데이터가 10000개 일 때 : 2.8012초

버블 정렬 vs 선택 정렬 vs 삽입 정렬

 

여러가지 상황의 데이터도 입력해보고, 데이터의 개수를 늘려가면서도 성능 테스트를 해본 결과 데이터의 정렬 상태와 데이터의 양에 따라서 결과가 모두 다르게 나왔다. 세 알고리즘 모두 O(n^2)의 시간 복잡도를 가지지만, 그 안에서도 다른 조건에 의해서 다른 결과치를 보여줬고, 만일 입력되는 데이터가 정렬되어 있다면 삽입 정렬의 시간 복잡도는 O(n)으로 압도적으로 빠른 시간을 보여줬다. 선택 정렬은 역순으로 정렬되어 있을 때 왼쪽부터 시작해서 배열의 끝까지 왔다갔다를 계속 해야 하므로 셋 중 가장 시간이 오래 걸린다는 걸 테스트 결과로도 확인했다.

이론상의 시간 복잡도와 실제 소요되는 시간에는 차이가 있다는 걸 알게 됐고, 이론상 결과만 보고 알고리즘을 사용하는게 아니라, 데이터의 상태에 맞춰서 어떤 알고리즘이 더 알맞을지 판단을 잘 해내는게 필요하다는 생각이다.