93 } while (swapped && n >= 1); |
93 } while (swapped && n >= 1); |
94 |
94 |
95 statistic ("Bubble"); |
95 statistic ("Bubble"); |
96 } |
96 } |
97 |
97 |
|
98 static int divide (int *v, int left, int right) |
|
99 { |
|
100 int i, j, pivot; |
|
101 |
|
102 i = left; |
|
103 j = right - 1; |
|
104 |
|
105 pivot = v[right]; |
|
106 |
|
107 do { |
|
108 while (v[i] <= pivot && i < right) { |
|
109 iters++; |
|
110 i++; |
|
111 } |
|
112 while (v[j] >= pivot && j > left) { |
|
113 iters++; |
|
114 j--; |
|
115 } |
|
116 if (i < j) { |
|
117 counter++; |
|
118 swap (v, i, j); |
|
119 } |
|
120 |
|
121 if (v[i] > pivot) { |
|
122 counter++; |
|
123 swap (v, i, right); |
|
124 } |
|
125 } while (i < j); |
|
126 |
|
127 return i; |
|
128 } |
|
129 |
|
130 void quicksort (int *v, int left, int right) |
|
131 { |
|
132 int divisor; |
|
133 |
|
134 if (left < right) { |
|
135 divisor = divide (v, left, right); |
|
136 quicksort (v, left, divisor - 1); |
|
137 quicksort (v, divisor + 1, right); |
|
138 } |
|
139 } |
|
140 |
98 int main (int argc, char **argv) |
141 int main (int argc, char **argv) |
99 { |
142 { |
100 int a[MAX]; |
143 int a[MAX]; |
101 int b[MAX]; |
144 int b[MAX]; |
102 int c[MAX]; |
145 int c[MAX]; |
103 int d[MAX]; |
146 int d[MAX]; |
|
147 int e[MAX]; |
104 |
148 |
105 int i; |
149 int i; |
106 |
150 |
107 srand (time (NULL)); |
151 srand (time (NULL)); |
108 |
152 |
111 } |
155 } |
112 |
156 |
113 memcpy (b, a, sizeof (a)); |
157 memcpy (b, a, sizeof (a)); |
114 memcpy (c, a, sizeof (a)); |
158 memcpy (c, a, sizeof (a)); |
115 memcpy (d, a, sizeof (a)); |
159 memcpy (d, a, sizeof (a)); |
|
160 memcpy (e, a, sizeof (a)); |
116 |
161 |
117 lazysort (a, MAX, &compare); |
162 lazysort (a, MAX, &compare); |
118 linearsort (b, MAX, &compare); |
163 linearsort (b, MAX, &compare); |
119 bubblesort (c, MAX, &compare); |
164 bubblesort (c, MAX, &compare); |
120 |
165 |
121 qsort (d, MAX, sizeof (int), (void *)&compare); |
166 quicksort (d, 0, MAX - 1); |
122 statistic ("Quick"); |
167 statistic ("mquick"); |
|
168 |
|
169 qsort (e, MAX, sizeof (int), (void *)&compare); |
|
170 statistic ("gquick"); |
123 |
171 |
124 printf ("PRESS <RETURN> to CONTINUE"); |
172 printf ("PRESS <RETURN> to CONTINUE"); |
125 while (getchar () != 10); |
173 while (getchar () != '\n'); |
126 printf ("%2c %2c %2c %2c\n-----------\n", 'L', 'N', 'B', 'Q'); |
|
127 |
174 |
|
175 printf ("%6c %6c %6c %6c %6c\n----------------------------------\n", 'L', 'N', 'B', 'M', 'G'); |
128 for (i = 0; i < MAX; i++) |
176 for (i = 0; i < MAX; i++) |
129 printf ("%2d %2d %2d %2d\n", a[i], b[i], c[i], d[i]); |
177 printf ("%6d %6d %6d %6d %6d\n", a[i], b[i], c[i], d[i], e[i]); |
130 |
178 |
131 return EXIT_SUCCESS; |
179 return EXIT_SUCCESS; |
132 } |
180 } |