개념 요약
- Selection Sort와 유사하지만, 더 효율적인 정렬 방법이다.
- 자료의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 방법이다.
정렬 과정
- 시작 인덱스를 2번째 인덱스부터 시작한다.
- 시작 인덱스 값과 이전의 인덱스 값을 비교하여 삽입한다.
- 시작 인덱스 + 1을 2번 과정으로 반복한다.
코드
void insertion_sort(std::vector<int> &unsorted_array)
{
int temp = 0, prev_idx = 0;
// 2번째 인덱스 부터 시작
for (int idx = 1; idx < unsorted_array.size(); ++idx)
{
// 현재 인덱스 값, 루프를 돌 인덱스 저장
temp = unsorted_array[idx];
prev_idx = idx - 1;
while (prev_idx >= 0 && unsorted_array[prev_idx] > temp)
{
// 뒤로 땡기기
unsorted_array[prev_idx + 1] = unsorted_array[prev_idx];
--prev_idx;
}
// 찾은 위치에 삽입
unsorted_array[prev_idx + 1] = temp;
}
}
시간 복잡도
- 최악의 경우는 $O(n^2)$이다.
- 하지만 모두 정렬되어있는 경우 $O(n)$이고 평균적으로 $O(n^2)$이다.
공간 복잡도
- 주어진 배열 내에서 swap 하므로 $O(n)$이다.
장단점
- 알고리즘이 단순하고 정렬되어있을 경우엔 매우 효율적이다.
- 버블 정렬, 선택 정렬보다 상대적으로 빠르며, 안정한 정렬이다.
- 평균, 최악의 시간 복잡도가 $O(n^2)$으로 비효율적이다.
'CS공부 > Algorithm' 카테고리의 다른 글
힙 정렬(Heap Sort) (0) | 2022.06.21 |
---|---|
병합 정렬(Merge Sort) (0) | 2022.06.21 |
퀵 정렬(Quick Sort) (0) | 2022.06.20 |
선택 정렬(Selection Sort) (0) | 2022.06.20 |
거품 정렬(Bubble Sort) (0) | 2022.06.20 |