[C] 삽입 정렬(Insertion Sort)

삽입 정렬(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)