[C 알고리즘] 삽입정렬 - Insertion Sort Algorithm

삽입정렬이 앞서 배운 선택정렬, 버블정렬과 차이점을 가지는게 있다면 그것은 '필요할때만'이라는 키워드다.

삽입정렬의 핵심은 각 숫자를 적절한 위치에 삽입하는 것인데, 여기서 필요할때만 위치를 바꾼다는 점 때문에 앞의 두 정렬보다는 속도가 빠르다. 하지만 여전히 O(N^2)의 속도로 느린 정렬 알고리즘에 속한다.

 

삽입정렬 알고리즘 떠올리기

앞의 숫자가 더 작다면 그 앞은 이미 정렬되어있는것이다.

앞의 숫자가 작을때까지 반복해야한다.

인덱스를 1씩 늘리며 각 인덱스마다 시행하며

그 시행에선 WHILE문을 시행한다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#pragma warning(disable:4996) #include <stdio.h>   void swap(int* p, int a, int b); /* T개의 정수를 입력받았을때 오름차순으로 정수들을 정렬해서 출력하시오*/   /* 삽입정렬의 핵심은 각 인덱스마다 시행하기때문에 특정 인덱스i에서 i와 i+1이 오름차순 정렬이 되어있다면 그 인덱스 앞은 이미 정렬되어있는 것이다. 앞의 시행에서 다 정렬해온것*/ int main() {     int N[1001];     int T;     scanf("%d", &T);       for(int p=0;p<T;p++){     scanf("%d",&N[p]);     }     //각 인덱스마다 시행한다.     for (int i = 0; i < T - 1; i++) {                    int j = i;           while (N[j] > N[j + 1]) {// 이미 오름차순 정렬인경우 종료한다. 종료조건2               swap(N, j, j + 1);             if (j == 0) break;// j가 0이면 종료한다. 종료조건1             j--;         }     }     for(int k=0;k<T;k++){         printf("%d ",N[k]);     } }     void swap(int* p, int a, int b) {       int temp=0;     temp = p[a];     p[a] = p[b];     p[b] = temp; } Colored by Color Scripter

cs