삽입 정렬)
두 번째 원소로 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자로를 삽입하여 정렬하는 알고리즘.
해당 배열을 오름차순으로 정렬한다면.
두 번쨰 요소를 시작으로 key이전의 요소들과 비교를 한다.
7보단 5가 더 작으므로 7을 밀고 5를 삽입한다.
2번째 요소를 정렬했기 때문에 3번쨰 요소인 1을 이전 요소들과 비교 시작.
7보다 1이 작기때문에 7을 이동, 1을 삽입.
2회전의 결과이다. 이 이후로도 같은 작업을 이어간다.
2번째 요소부터 시작하지만 1번째 요소까지 계속 비교하며 N to 1 까지 비교해나간다.
삽입 정렬의 특징
- 배열 내에서 교환하는 방식으로, 공간복잡도는 O(1)이다. 추가적인 부분은 원소를 교환할때 사용하는 임시요소정도.
- 평균과 최악의 시간복잡도는 O(n^2)
- 삽입 정렬은 중복된 키 값의 순서가 정렬된 후에도 유지되므로 stable정렬이다.
- 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다,
소스코드
void insertionsort(double arr[], int N){
int i, j, cur_el;
for(i = 1; i < N; i++){
j = i;
cur_el = arr[j];
while((i >= 1) && arr[j-1]>cur_el){
arr[j] = arr[j-1];
j--;
}
arr[j] = cur_el;
}
}실행결과
해당 자료는 랜덤한 데이터를 만들어서 처리한 결과이며, 시스템에 따라 다를 수 있음.
| 자료 개수 | 처리시간 |
| 10000 | 0.000374 |
| 100000 | 0.003652 |
| 1000000 | 0.021501 |
| 100000000 | 2.292645 |