삽입 정렬(Insertion Sort)
삽입 정렬?
삽입 정렬은 이미정렬된 앞부분의 항들과 비교해서
사이에 작은 수를 삽입하여 정렬하는 방법입니다.
아래 위키백과의 애니메이션을 보면 쉽게 이해할 수 있습니다.
https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
복잡도
삽입정렬의 복잡도는 아래와 같습니다.
배열을 이용한 삽입 정렬 예제
삽입 정렬 함수
기준항(temp)와 정렬된 앞 요소들의 크기를 비교하고 한칸 씩 뒤로 옮긴 후 기준항을 삽입합니다.
두 번째 항부터 비교를 시작하므로 i는 1부터 시작합니다.
void insertion_sort(int array[], int size){
int j,temp;
for(int i=1; i<size; i++){
j=i;
temp = array[i];
while(j>0 && array[j-1]>temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}
실행 함수
정렬 전과 후 배열 출력
void main(){
int array[] = {11,10,33,22,55,9};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
insertion_sort(array,size);
printf("\n########### Sorting after ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
}
실행 결과
참고 : C로 배우는 알고리즘 (이재규)
위키백과(삽입정렬)
관련 포스팅
[DataStructure] 기수 정렬(Radix Sort)
[DataStructure] 퀵 정렬(Quick Sort)
[DataStructure] 셸 정렬(Shell Sort)
[DataStructure] 버블 정렬(Bubble Sort)
[DataStructure] 삽입 정렬(Insertion Sort)
[DataStructure] 선택 정렬(Selection Sort)
'언어 > Data Strcuture' 카테고리의 다른 글
| [C] 셸 정렬(Shell Sort) (2) | 2019.04.23 |
|---|---|
| [C] 버블 정렬(Bubble Sort) (0) | 2019.04.20 |
| [C] 선택 정렬(Selection Sort) (0) | 2019.04.19 |
| [C] 트리(Tree) (0) | 2019.04.07 |
| [C] 큐(Queue) (2) | 2019.04.01 |