이 글은 이것이 취업을 위한 코딩테스트다 with python편을 보고 작성하였습니다.
삽입 정렬 개요
삽입 정렬은 '데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 방식'의 정렬 알고리즘입니다.
선택 정렬 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬을 그렇지 않아서 선택 정렬에 비해 실행 시간 측면에서 더 효율적입니다.
특히, 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씩 효율적입니다.
삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(Insertion Sort)라고 부릅니다.
1. 삽입 정렬 예시
삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정합니다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입한다는 특징이 있습니다. 그렇기에 첫 번째 데이터는 정렬되어 있다고 판단하고 두 번째 데이터부터 시작합니다.
정렬된 데이터는 하늘색으로, 현재 처리하는 데이터는 회색으로 표시하겠습니다.
- 첫 번째 데이터 '3'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '2'가 어떤 위치로 들어갈지 판단합니다. '3'의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재합니다. 예시에서는 오름차순으로 정렬하고자 '3'의 왼쪽에 삽입합니다.
- 이어서 '4'가 어떤 위치에 들어갈지 판단합니다. 삽입될 수 있는 위치는 총 3가지이며 현재 '4'는 '2'와 '3'보다 크기에 원래 자리 그대로 둡니다.
- 이어서 '1'이 어떤 위치에 들어갈지 판단합니다. '1'은 '2', '3', '4'와 비교했을 때 가장 작기에 첫 번째 위치에 삽입합니다.
- 이어서 '0'이 어떤 위치에 들어갈지 판단합니다. '0'은 '1', '2', '3', '4'와 비교했을 때 가장 작기에 첫 번째 위치에 삽입합니다.
- 데이터의 개수가 많아도 위와 같이 적절한 위치에 삽입하는 과정을 N - 1번 반복하게 되면 다음과 같이 모든 데이터가 정렬됩니다.
삽입 정렬은 특징이 있는데, 정렬이 이루어진 원소(그림에서 하늘색)는 항상 오름차순을 유지하고 있습니다. 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에 멈추면 됩니다.
2. 삽입 정렬 코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
# 첫 번째 원소는 정렬되었다고 가정하기에 두 번째 원소부터 확인
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 자리에서 멈춤
break
print(array)- range의 매개 변수는 (start, end, step) 입니다. 세 번째 매개 변수인 step에 -1을 넣어 start 인덱스부터 end + 1 인덱스까지 -1씩 감소합니다.
3. 삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되어서 그렇습니다. 하지만 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다. 최선의 경우 O(N)의 시간 복잡도를 가집니다.
따라서 만약 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 더 빠를 수도 있습니다.
