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