1. 삽입 정렬 개념
이미 정렬되어 있는 배열에 새로운 수를 추가하는 것은 아주 간단합니다.
이런 방법을 바탕으로 범위를 늘려가며, 다음 원소를 이미 정렬된 범위 안에 삽입하는 방식으로 정렬합니다.
마치 손 안의 카드를 정렬하는 방법과 유사합니다.
2. 삽입 정렬 예제
삽입 위치를 찾기 위해 정렬되어 있는 부분을 탐색하는 과정을 위 그림을 통해 볼 수 있습니다.
이 과정을 이분 탐색으로 \(O(\log{n})\)의 시간에 빠르게 찾을 수 있을 것 같습니다.
하지만 선택한 원소를 해당 위치에 삽입하기 위해서는 뒤쪽의 모든 원소를 한 자리씩 옮겨야하므로 결국 \(O(n)\)만큼의 시간이 소요되어 의미가 없어집니다.
3. 삽입 정렬 코드
nums = [5, 3, 4, 1, 2]
def insertion_sort(nums):
for i in range(1, len(nums)):
num = nums[i]
j = i-1
while j >= 0 and nums[j] > num:
nums[j+1] = nums[j]
j -= 1
nums[j+1] = num
insertion_sort(nums)
print(nums)
# [1, 2, 3, 4, 5]4. 삽입 정렬 장점
삽입 정렬은 이해하기 쉬운 알고리즘이기 때문에 구현도 쉽습니다.
데이터의 개수가 적을 때 매우 효율적입니다.
내부 루프에서 앞의 부분 배열이 이미 정렬 되어있다면 한 번의 비교로 끝이 납니다. 따라서 최선의 경우에 외부 루프만 반복하므로 \(O(n)\) 만에 정렬이 끝납니다.
그러므로 이미 대부분 정렬되어 있는 배열에서 매우 효율적입니다.
동일한 값을 가지는 원소는 자리가 바뀌지 않으므로 안정적인 정렬입니다.
배열 안에서 정렬이 이루어지는 제자리 정렬이므로 추가적인 메모리를 거의 사용하지 않습니다.
5. 삽입 정렬 단점
최악, 평균의 시간 복잡도는 \(O(n^2)\)으로 데이터의 개수가 많아지면 성능이 급격히 저하됩니다.
데이터의 이동이 많이 발생하므로 비효율적입니다.
6. 정렬 알고리즘 시간 복잡도 비교
| 정렬 알고리즘 | 최악(Worst) | 최선(Best) | 평균(Average) |
| 버블 정렬(Bubble Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 선택 정렬(Selection Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 삽입 정렬(Insertion Sort) | \(\boldsymbol{O(n^2)}\) | \(\boldsymbol{O(n)}\) | \(\boldsymbol{O(n^2)}\) |
| 퀵 정렬(Quick Sort) | \(O(n^2)\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 병합 정렬(Merge Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 힙 정렬(Heap Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 기수 정렬(Radix Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
| 계수 정렬(Counting Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
