| Inhalt | Code | Beispiel |
| C | Kommentare | Zeilennummern | Midnight |
001 /* Author Malte Pagel */
002
003 #include <stdio.h>
004 #include <stdlib.h>
005 #include <time.h>
006 #include <math.h>
007
008
009 #define NUM_ELEMENTS 500000
010 #define LIMIT 5000000
011
012 #define DEBUG_OUTPUT 0
013
014
015 int elements[NUM_ELEMENTS];
016
017 struct list_element {
018 int value;
019 struct list_element *previous;
020 struct list_element *next;
021 };
022 struct list_element *global_first_element;
023 struct list_element *global_last_element;
024 struct element_pair {
025 struct list_element *first;
026 struct list_element *last;
027 };
028
029
030 void show_elements(int[], int);
031 void show_list_elements(struct list_element*, struct list_element*);
032 void show_partially_sorted_list(struct list_element*, struct list_element*, struct list_element*, struct list_element*, struct list_element*);
033
034 int std_compare(const void*, const void*);
035
036 void fill_elements(int);
037
038
039 struct element_pair reverse_list(struct list_element**, struct list_element**);
040 struct element_pair surreal_sort(struct list_element**, struct list_element**);
041
042
043 /* */
044
045 void show_elements (int the_elements[], int num) {
046 int i;
047 for ( i = 0; i < num; i++ )
048 if ( i < (num - 1) )
049 printf("%d, ", the_elements[i]);
050 else
051 printf("%d", the_elements[i]);
052 printf("\n");
053 }
054 void show_list_elements(struct list_element* first, struct list_element* last) {
055 struct list_element *actual = first;
056
057 while ( actual != NULL ) {
058 printf("%d", actual->value);
059 if ( actual == last )
060 break;
061 printf(", ");
062 actual = actual->next;
063 }
064 printf("\n");
065 }
066 void show_partially_sorted_list (struct list_element* first, struct list_element* low_left, struct list_element* low_right, struct list_element* high_left, struct list_element* high_right) {
067
068 struct list_element *actual = first;
069 int special_element = 0;
070
071 while ( actual != NULL ) {
072
073 if ( actual == low_left || actual == high_left )
074 special_element = 1;
075
076 if ( special_element )
077 printf("(%d)", actual->value);
078 else
079 printf("%d", actual->value);
080
081 if ( actual->next == NULL )
082 break;
083 if ( !special_element )
084 printf(", ");
085
086 if ( actual == low_right || actual == high_right )
087 special_element = 0;
088
089 actual = actual->next;
090 }
091 printf("\n");
092 }
093
094 /* */
095
096 int std_compare (const void* value1, const void* value2) {
097 return (*(int*)value1 - *(int*)value2);
098 }
099
100 /* */
101
102
103 void fill_elements (int method) {
104
105 int i, distance, index, add, count, remember;
106 int indices[NUM_ELEMENTS];
107
108 distance = LIMIT / NUM_ELEMENTS;
109
110 switch (method) {
111 case 1:
112 elements[0] = rand() % distance + 1;
113 for ( i = 1; i < NUM_ELEMENTS; i++ )
114 elements[i] = elements[i - 1] + (rand() % distance);
115 break;
116 case 2:
117 elements[0] = LIMIT - (rand() % distance + 1);
118 for ( i = 1; i < NUM_ELEMENTS; i++ )
119 elements[i] = elements[i - 1] - (rand() % distance);
120 break;
121 case 3:
122 for ( i = 0; i < NUM_ELEMENTS; i++ )
123 elements[i] = (rand() % LIMIT) + 1;
124 break;
125 case 4:
126 for ( i = 0; i < NUM_ELEMENTS; i++ )
127 indices[i] = i;
128 for ( count = 0; count < sqrt((double) NUM_ELEMENTS); count++ ) {
129 add = rand() % (NUM_ELEMENTS / 2) + (NUM_ELEMENTS / 4);
130 index = rand() % (NUM_ELEMENTS / 2) + (NUM_ELEMENTS / 4);
131 for ( i = 0; i < NUM_ELEMENTS; i++ ) {
132 remember = indices[i];
133 if ( count % 2 == 0 ) {
134 indices[i] = indices[(i + add) % NUM_ELEMENTS];
135 indices[(i + add) % NUM_ELEMENTS] = remember;
136 } else {
137 indices[i] = indices[(NUM_ELEMENTS + i - add) % NUM_ELEMENTS];
138 indices[(NUM_ELEMENTS + i - add) % NUM_ELEMENTS] = remember;
139 }
140 }
141 }
142 for ( i = 0; i < NUM_ELEMENTS; i++ )
143 elements[i] = (indices[i] + 1) * distance;
144 break;
145 }
146
147 global_first_element = malloc(sizeof(struct list_element));
148 global_first_element->value = elements[0];
149 global_first_element->previous = NULL;
150
151 struct list_element *tmp = global_first_element;
152 for ( i = 1; i < NUM_ELEMENTS; i++ ) {
153 tmp->next = malloc(sizeof(struct list_element));
154 tmp->next->value = elements[i];
155 tmp->next->previous = tmp;
156 tmp = tmp->next;
157 }
158 tmp->next = NULL;
159 global_last_element = tmp;
160 }
161
162 /* */
163
164 struct element_pair reverse_list (struct list_element **first_element, struct list_element **last_element) {
165
166 struct list_element *first = *first_element;
167 struct list_element *last = *last_element;
168
169 //struct list_element *before = first->previous;
170 struct list_element *after = last->next;
171
172 struct list_element *tmp = first;
173 struct list_element *tmp_next;
174
175 while ( tmp && tmp != after ) {
176 tmp_next = tmp->next;
177 tmp->next = tmp->previous;
178 tmp->previous = tmp_next;
179 tmp = tmp_next;
180 }
181
182 //before->next = last;
183 //last->previous = before;
184 //after->previous = first;
185 //first->next = after;
186
187 struct element_pair solution;
188
189 solution.first = last;
190 solution.last = first;
191
192 return solution;
193 }
194 struct element_pair surreal_sort (struct list_element **first, struct list_element **last) {
195
196 struct element_pair solution;
197 solution.first = *first;
198 solution.last = *last;
199
200 struct list_element *first_element = *first;
201 struct list_element *last_element = *last;
202 struct list_element *low_left = *first;
203 struct list_element *low_right = *first;
204 struct list_element *high_left = *last;
205 struct list_element *high_right = *last;
206 struct list_element *low_tmp = NULL;
207 struct list_element *high_tmp = NULL;
208
209 first_element->previous = NULL;
210 last_element->next = NULL;
211
212 int direction_counter;
213 struct element_pair tmp_solution;
214
215
216 if ( first_element == last_element )
217 return solution;
218 if ( first_element->next == last_element ) {
219 if ( first_element->value <= last_element->value )
220 return solution;
221 else {
222 last_element->previous = NULL;
223 last_element->next = first_element;
224 first_element->previous = last_element;
225 first_element->next = NULL;
226 solution.first = last_element;
227 solution.last = first_element;
228 return solution;
229 }
230 }
231
232
233 if ( first_element->value > last_element->value ) {
234 low_tmp = first_element->next;
235 high_tmp = last_element->previous;
236 low_tmp->previous = last_element;
237 last_element->next = low_tmp;
238 high_tmp->next = first_element;
239 first_element->previous = high_tmp;
240 first_element = low_tmp->previous;
241 last_element = high_tmp->next;
242 first_element->previous = NULL;
243 last_element->next = NULL;
244
245 low_left = first_element;
246 low_right = first_element;
247 high_left = last_element;
248 high_right = last_element;
249 }
250
251
252 /* */
253
254 while ( 1 ) {
255
256 // LEFT SIDE
257 low_tmp = low_right->next;
258
259 if ( low_tmp == high_left )
260 break;
261
262 if ( low_tmp->value >= low_right->value && low_tmp->value <= high_left->value ) { // inside middle; ordered
263 low_right = low_tmp;
264 while ( low_right->next != high_left && low_right->next->value >= low_right->value && low_right->next->value <= high_left->value )
265 low_right = low_right->next;
266 } else {
267 high_tmp = low_tmp;
268 direction_counter = 0;
269 if ( low_tmp->value < low_right->value ) { // small
270 if ( low_tmp->value < low_left->value ) { // very small
271 while ( high_tmp->next != high_left && high_tmp->next->value < low_left->value ) {
272 direction_counter += (high_tmp->next->value < high_tmp->value) ? -1 : 1;
273 high_tmp = high_tmp->next;
274 }
275
276 low_tmp->previous->next = high_tmp->next;
277 high_tmp->next->previous = low_tmp->previous;
278 if ( direction_counter < 0 )
279 tmp_solution = reverse_list(&low_tmp, &high_tmp);
280 else {
281 tmp_solution.first = low_tmp;
282 tmp_solution.last = high_tmp;
283 }
284 tmp_solution.last->next = first_element;
285 first_element->previous = tmp_solution.last;
286 first_element = tmp_solution.first;
287 first_element->previous = NULL;
288 } else { // inside left ordered part
289 while ( high_tmp->next != high_left && high_tmp->next->value < low_right->value && high_tmp->next->value >= low_left->value )
290 high_tmp = high_tmp->next;
291
292 low_right->previous->next = low_right->next;
293 low_right->next->previous = low_right->previous;
294 low_right->next = high_tmp->next;
295 low_right->next->previous = low_right;
296 high_tmp->next = low_right;
297 low_right->previous = high_tmp;
298
299 low_left = low_right;
300 }
301 } else { // high
302 if ( low_tmp->value > high_right->value ) { // very high
303 while ( high_tmp->next != high_left && high_tmp->next->value > high_right->value ) {
304 direction_counter += (high_tmp->next->value < high_tmp->value) ? -1 : 1;
305 high_tmp = high_tmp->next;
306 }
307
308 low_tmp->previous->next = high_tmp->next;
309 high_tmp->next->previous = low_tmp->previous;
310 if ( direction_counter < 0 )
311 tmp_solution = reverse_list(&low_tmp, &high_tmp);
312 else {
313 tmp_solution.first = low_tmp;
314 tmp_solution.last = high_tmp;
315 }
316 tmp_solution.first->previous = last_element;
317 last_element->next = tmp_solution.first;
318 last_element = tmp_solution.last;
319 last_element->next = NULL;
320 } else { // inside right ordered part
321 while ( high_tmp->next != high_left && high_tmp->next->value > high_left->value && high_tmp->next->value <= high_right->value )
322 high_tmp = high_tmp->next;
323
324 low_tmp->previous->next = high_tmp->next;
325 high_tmp->next->previous = low_tmp->previous;
326 high_left->next->previous = high_tmp;
327 high_tmp->next = high_left->next;
328 high_left->next = low_tmp;
329 low_tmp->previous = high_left;
330
331 high_right = high_left;
332 }
333 }
334 }
335
336 // RIGHT SIDE
337 high_tmp = high_left->previous;
338
339 if ( high_tmp == low_right )
340 break;
341
342 high_tmp = high_left->previous;
343
344 if ( high_tmp->value >= low_right->value && high_tmp->value <= high_left->value ) { // inside middle; ordered
345 high_left = high_tmp;
346 while ( high_left->previous != low_right && high_left->previous->value <= high_left->value && high_left->previous->value >= low_right->value )
347 high_left = high_left->previous;
348 } else {
349 low_tmp = high_tmp;
350 direction_counter = 0;
351 if ( high_tmp->value < low_right->value ) { // small
352 if ( high_tmp->value < low_left->value ) { // very small
353 while ( low_tmp->previous != low_right && low_tmp->previous->value < low_left->value ) {
354 direction_counter += (low_tmp->previous->value > low_tmp->value) ? -1 : 1;
355 low_tmp = low_tmp->previous;
356 }
357
358 low_tmp->previous->next = high_tmp->next;
359 high_tmp->next->previous = low_tmp->previous;
360 if ( direction_counter < 0 )
361 tmp_solution = reverse_list(&low_tmp, &high_tmp);
362 else {
363 tmp_solution.first = low_tmp;
364 tmp_solution.last = high_tmp;
365 }
366 tmp_solution.last->next = first_element;
367 first_element->previous = tmp_solution.last;
368 first_element = tmp_solution.first;
369 first_element->previous = NULL;
370 } else { // inside left ordered part
371 while ( low_tmp->previous != low_right && low_tmp->previous->value < low_right->value && low_tmp->previous->value >= low_left->value )
372 low_tmp = low_tmp->previous;
373
374 low_tmp->previous->next = high_tmp->next;
375 high_tmp->next->previous = low_tmp->previous;
376 low_right->previous->next = low_tmp;
377 low_tmp->previous = low_right->previous;
378 high_tmp->next = low_right;
379 low_right->previous = high_tmp;
380
381 low_left = low_right;
382 }
383 } else { // high
384 if ( high_tmp->value > high_right->value ) { // very high
385 while ( low_tmp->previous != low_right && low_tmp->previous->value > high_right->value ) {
386 direction_counter += (low_tmp->previous->value > low_tmp->value) ? -1 : 1;
387 low_tmp = low_tmp->previous;
388 }
389
390 low_tmp->previous->next = high_tmp->next;
391 high_tmp->next->previous = low_tmp->previous;
392 if ( direction_counter < 0 )
393 tmp_solution = reverse_list(&low_tmp, &high_tmp);
394 else {
395 tmp_solution.first = low_tmp;
396 tmp_solution.last = high_tmp;
397 }
398 tmp_solution.first->previous = last_element;
399 last_element->next = tmp_solution.first;
400 last_element = tmp_solution.last;
401 last_element->next = NULL;
402 } else {
403 while ( low_tmp->previous != low_right && low_tmp->previous->value > high_left->value && low_tmp->previous->value <= high_right->value )
404 low_tmp = low_tmp->previous;
405
406 high_left->next->previous = high_left->previous;
407 high_left->previous->next = high_left->next;
408 high_left->previous = low_tmp->previous;
409 high_left->previous->next = high_left;
410 low_tmp->previous = high_left;
411 high_left->next = low_tmp;
412
413 high_right = high_left;
414 }
415 }
416 }
417
418 }
419
420 /* */
421
422 if ( low_left->previous ) {
423 tmp_solution = surreal_sort(&first_element, &low_left->previous);
424
425 first_element = tmp_solution.first;
426 //first_element->previous = NULL;
427 tmp_solution.last->next = low_left;
428 low_left->previous = tmp_solution.last;
429 }
430
431 if ( high_right->next ) {
432 tmp_solution = surreal_sort(&high_right->next, &last_element);
433
434 last_element = tmp_solution.last;
435 //last_element->next = NULL;
436 tmp_solution.first->previous = high_right;
437 high_right->next = tmp_solution.first;
438 }
439
440
441 solution.first = first_element;
442 solution.last = last_element;
443
444 return solution;
445 }
446
447
448 int main (int argc, const char * argv[]) {
449
450 global_first_element = NULL;
451 global_last_element = NULL;
452 struct element_pair solution;
453
454 clock_t start, end;
455 double used_time;
456
457 time_t t;
458 time(&t);
459 srand((unsigned int) t);
460
461
462 char c = '?';
463
464 char welcome[] = "\t 1 - Ascending\n\t 2 - Decending\n\t 3 - Random\n\t 4 - Cards\n\t q - Quit\n";
465
466 printf("\n%s\n", welcome);
467
468 while ( c != '1' && c != '2' && c != '3' && c != '4' && c != 'q' && c != 'Q' ) {
469 scanf("%s", &c);
470 if ( c != '1' && c != '2' && c != '3' && c != '4' && c != 'q' && c != 'Q' )
471 printf("\nOnce again!\n%s", welcome);
472 }
473
474 if ( c == 'q' || c == 'Q' )
475 return 0;
476
477
478 fill_elements(c - 48);
479
480 printf("\n");
481
482
483 if ( DEBUG_OUTPUT )
484 show_elements(elements, NUM_ELEMENTS);
485 //show_list_elements(global_first_element, global_last_element);
486
487 start = clock();
488 qsort(elements, NUM_ELEMENTS, sizeof(int), std_compare);
489 end = clock();
490 used_time = (float) (end - start) / (float) CLOCKS_PER_SEC;
491 if ( !DEBUG_OUTPUT )
492 printf("\n\t %d elements sorted using qsort() in %.2f seconds", NUM_ELEMENTS, used_time);
493
494 start = clock();
495 solution = surreal_sort(&global_first_element, &global_last_element);
496 end = clock();
497 used_time = (float) (end - start) / (float) CLOCKS_PER_SEC;
498 if ( !DEBUG_OUTPUT )
499 printf("\n\t %d elements sorted using surreal_sort() in %.2f seconds \n\n", NUM_ELEMENTS, used_time);
500
501
502 //show_elements(elements, NUM_ELEMENTS);
503 if ( DEBUG_OUTPUT )
504 show_list_elements(solution.first, solution.last);
505
506
507 global_first_element = global_first_element->next;
508 while ( global_first_element ) {
509 free(global_first_element->previous);
510 global_first_element = global_first_element->next;
511 }
512 free(solution.last);
513
514
515
516
517 return 0;
518 }
519