삽입정렬(Insertion-Sort)

삽입 정렬 (Insertion-Sort)

- 삽입 정렬은 복잡도가 O(n^2)인 느린 알고리즘이다.

- 정렬 되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입하며 정렬하는 알고리즘이다.

동작 원리

- 처음 배열의 두번째 원소를 키값으로 설정하고 자신의 앞부분 배열의 원소들과 비교해 자신의 자리를 찾는다

- 자신의 자리를 찾은 곳에 원소를 배치한다

- 다음 원소를 키값으로 앞부분의 배열의 원소들과 비교해 자신의 자리를 찾아나가 배열의 정렬을 한다.

소스 

1. #include<stdio.h>
2.  
3. int main(void)
4. {
5.     int arr[5] = {5,4,3,1,2};
6.     int key =   0;
7.     int temp =  1;
8.     int temp2 = 0;
9.     int dis =   0;
10.    
11.     for(;temp < 5; temp++)
12.     {
13.         key = arr[temp];
14.         temp2  = temp - 1;
15.  
16.         while(arr[temp2] > key && temp2 >=0)
17.         {
18.             arr[temp2+1] = arr[temp2];
19.             temp2 --;
20.         }
21.  
22.         arr[temp2+1] = key;
23.  
24.  
25.     }
26.  
27.     for(dis = 0; dis<5;dis++)
28.     {
29.         printf("%d ",arr[dis]);
30.     }      
31.     printf("\n");
32.  
33.     return 0;
34. }

결과