Page 215 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

19 int i, nx;
20 int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
21 puts("단순 삽입 정렬");
22
23 printf("요소 개수 : ");
24 scanf("%d", &nx);
25 x = calloc(nx, sizeof(int)); /* 요소의 개수가 nx인 int형 배열을 생성 */
26
27 for(i = 0; i < nx; i++) {
28 printf("x[%d] : ", i);
29 scanf("%d", &x[i]);
30 }
31
32 insertion(x, nx); /* 배열 x를 단순 삽입 정렬 */
33
34 puts("오름차순으로 정렬했습니다.");
35 for(i = 0; i < nx; i++)
36 printf("x[%d] = %d\n", i, x[i]);
37
38 free(x); /* 배열을 해제 */
39
40 return 0;
41 }

이렇게 구현한 단순 삽입 정렬 알고리즘은 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적
2
입니다. 요소의 비교 횟수와 교환 횟수는 n / 2회입니다.
단순 삽입 정렬은 셔틀 정렬(shuttle sort)이라고도 합니다.

단순 정렬의 시간 복잡도
2
지금까지 공부한 세 가지 단순 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n )입니다(효율이
좋지 않습니다). 다음 절부터는 이런 정렬 알고리즘의 개선 방법을 알아보겠습니다.

06•정렬 215