1: // 삽입정렬
2: #include <stdio.h>
3: #include <sys/time.h>
4:
5: #define ASIZE 50000
6:
7: void ExChange(int *, int *);
8: void InputArray(int *, int);
9: void PrintArray(int *, int);
10: void BubbleSort(int *, int);
11: void InsertSort(int *, int);
12: void SelectionSort(int *, int);
13: static inline long myclock();
14:
15: int main()
16: {
17: int A[ASIZE];
18: int i;
19: int j;
20: int iMenu;
21: long t, dt;
22:
23: printf("정렬법을 선택하삼 (0 = 선택, 1 = 버블, 2 = 삽입)");
24: scanf("%d", &iMenu);
25:
26: // 배열 초기화
27: for(i = 0 ; i < ASIZE ; ++i)
28: {
29: A[i] = ASIZE - i; // 최악의 조건
30: }
31:
32: t = myclock();
33:
34: // 정렬
35: switch(iMenu)
36: {
37: case 0: // 선택정렬
38: SelectionSort(A, ASIZE);
39: break;
40:
41: case 1: // 버블정렬
42: BubbleSort(A, ASIZE);
43: break;
44:
45: case 2: // 삽입정렬
46: InsertSort(A, ASIZE);
47: break;
48:
49: default:
50: break;
51: }
52:
53: dt = myclock() - t;
54:
55: printf("\n소요시간 = %dsec %dusec \n", dt / 1000000, dt);
56: putchar('\n');
57:
58: return 0;
59: }
60:
61: // 값 교환
62: void ExChange(int *ipNum1, int *ipNum2)
63: {
64: int iTemp;
65:
66: iTemp = *ipNum1;
67: *ipNum1 = *ipNum2;
68: *ipNum2 = iTemp;
69:
70: return ;
71: }
72:
73: // 배열입력
74: void InputArray(int *ip, int iSize)
75: {
76: int iCnt;
77:
78: for(iCnt = 0 ; iCnt < iSize ; ++iCnt)
79: {
80: scanf("%d", (ip + iCnt));
81: }
82:
83: return ;
84: }
85:
86: // 배열출력
87: void PrintArray(int *ip, int iSize)
88: {
89: int iCnt;
90:
91: for(iCnt = 0 ; iCnt < iSize ; ++iCnt)
92: {
93: printf("%d, ", ip[iCnt]);
94: }
95: printf("\b\b \n");
96:
97: return ;
98: }
99:
100: // 선택정렬 - 배열주소, 사이즈를 인자로 받음.
101: void SelectionSort(int *ip, int iSize)
102: {
103: int i;
104: int j;
105:
106: for(i = 0 ; i < iSize - 1 ; ++i)
107: {
108: for(j = i + 1 ; j < iSize ; ++j)
109: {
110: if(ip[i] > ip[j])
111: {
112: ExChange(&ip[i], &ip[j]);
113: }
114: }
115: }
116:
117: return ;
118: }
119:
120:
121: // 버블정렬 - 배열주소, 사이즈를 인자로 받음.
122: void BubbleSort(int *ip, int iSize)
123: {
124: int i;
125: int j;
126: int iBreak;
127:
128: for(i = iSize - 1 ; 0 < i ; --i) // 4, 3, 2, 1
129: {
130: iBreak = 1; // 정렬플래그
131:
132: for(j = 0 ; i > j ; ++j) // 0 ~ (i - 1)
133: {
134: if(ip[j] > ip[j + 1]) // 오름차순정렬
135: {
136: ExChange(&ip[j], &ip[j + 1]); // 값 교환
137: iBreak = 0; // 정렬이 덜 되었다.
138: }
139: }
140:
141: if(1 == iBreak) // 정렬이 다 되면 그만해~
142: {
143: break;
144: }
145: }
146:
147: return ;
148: }
149:
150: // 삽입정렬 - 배열주소, 사이즈를 인자로 받음
151: void InsertSort(int *ip, int iSize)
152: {
153: int i;
154: int j;
155:
156: for(i = 1 ; iSize > i ; ++i)
157: {
158: for(j = i ; 0 < j ; --j)
159: {
160: if(ip[j] < ip[j - 1])
161: {
162: ExChange(&ip[j], &ip[j - 1]);
163: }
164: else
165: {
166: break;
167: }
168: }
169: }
170:
171: return ;
172: }
173:
174: // 현재 시간 측정함수
175: static inline long myclock()
176: {
177: struct timeval tv;
178: gettimeofday(&tv, NULL);
179: return (tv.tv_sec * 1000000 + tv.tv_usec);
180: }
181:
