38 printf ("%8s finished after %10lu swaps and %10lu Iterations.\n", func, counter, iters); |
38 printf ("%8s finished after %10lu swaps and %10lu Iterations.\n", func, counter, iters); |
39 counter = iters = 0; |
39 counter = iters = 0; |
40 } |
40 } |
41 |
41 |
42 /** |
42 /** |
43 * Laufzeitverhalten: n^2-1 Durchläufe zum Sortieren von n Elementen... |
43 * Laufzeitverhalten: n^2-n Durchläufe zum Sortieren von n Elementen... |
44 */ |
44 */ |
45 void lazysort (int *v, int n, int (*compare_func) (int *, int *)) |
45 void lazysort (int *v, int n, int (*compare_func) (int *, int *)) |
46 { |
46 { |
47 int i, j; |
47 int i, j; |
48 |
48 |
55 } |
55 } |
56 statistic ("Lazy"); |
56 statistic ("Lazy"); |
57 } |
57 } |
58 |
58 |
59 /** |
59 /** |
60 * Laufzeitverhalten: (1/2)*n^2-1 Durchläufe zum Sortieren von n Elementen... |
60 * Laufzeitverhalten: (1/2)*n^2-n Durchläufe zum Sortieren von n Elementen... |
61 */ |
61 */ |
62 void bubblesort (int *v, int n, int (*compare) (int *, int *)) |
62 void linearsort (int *v, int n, int (*compare) (int *, int *)) |
63 { |
63 { |
64 int i, j; |
64 int i, j; |
65 |
65 |
66 for (i = (n - 1); i > 0; i--) { |
66 for (i = (n - 1); i > 0; i--) { |
67 for (j = 1; j <= i; j++) { |
67 for (j = 1; j <= i; j++) { |
68 if (compare (&v[j - 1], &v[j])) { |
68 if (compare (&v[j - 1], &v[j])) { |
69 swap (v, j - 1, j); |
69 swap (v, j - 1, j); |
70 } |
70 } |
71 } |
71 } |
72 } |
72 } |
|
73 statistic ("Linear"); |
|
74 } |
|
75 |
|
76 /** |
|
77 * Laufzeitverhalten: ~(1/{2|4})*n^2-n Durchläufe zum Sortieren... |
|
78 */ |
|
79 void bubblesort (int *v, int n, int (*compare) (int *, int *)) |
|
80 { |
|
81 int i; |
|
82 int swapped; |
|
83 |
|
84 do { |
|
85 swapped = 0; |
|
86 for (i = 1; i < n; i++) { |
|
87 if (compare (&v[i - 1], &v[i])) { |
|
88 swap (v, i, i - 1); |
|
89 swapped = 1; |
|
90 } |
|
91 } |
|
92 n--; |
|
93 } while (swapped && n >= 1); |
|
94 |
73 statistic ("Bubble"); |
95 statistic ("Bubble"); |
74 } |
96 } |
75 |
97 |
76 int main (int argc, char **argv) |
98 int main (int argc, char **argv) |
77 { |
99 { |
78 int a[MAX]; |
100 int a[MAX]; |
79 int b[MAX]; |
101 int b[MAX]; |
80 int c[MAX]; |
102 int c[MAX]; |
|
103 int d[MAX]; |
81 |
104 |
82 int i; |
105 int i; |
83 |
106 |
84 srand (time (NULL)); |
107 srand (time (NULL)); |
85 |
108 |
87 a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0)); |
110 a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0)); |
88 } |
111 } |
89 |
112 |
90 memcpy (b, a, sizeof (a)); |
113 memcpy (b, a, sizeof (a)); |
91 memcpy (c, a, sizeof (a)); |
114 memcpy (c, a, sizeof (a)); |
|
115 memcpy (d, a, sizeof (a)); |
92 |
116 |
93 lazysort (a, MAX, &compare); |
117 lazysort (a, MAX, &compare); |
94 bubblesort (b, MAX, &compare); |
118 linearsort (b, MAX, &compare); |
|
119 bubblesort (c, MAX, &compare); |
95 |
120 |
96 qsort (c, MAX, sizeof (int), (void *)&compare); |
121 qsort (d, MAX, sizeof (int), (void *)&compare); |
97 statistic ("Quick"); |
122 statistic ("Quick"); |
98 |
123 |
99 printf ("PRESS <RETURN> to CONTINUE"); |
124 printf ("PRESS <RETURN> to CONTINUE"); |
100 while (getchar () != 10); |
125 while (getchar () != 10); |
101 printf ("%2c %2c %2c\n--------\n", 'L', 'B', 'Q'); |
126 printf ("%2c %2c %2c %2c\n-----------\n", 'L', 'N', 'B', 'Q'); |
102 |
127 |
103 for (i = 0; i < MAX; i++) |
128 for (i = 0; i < MAX; i++) |
104 printf ("%2d %2d %2d\n", a[i], b[i], c[i]); |
129 printf ("%2d %2d %2d %2d\n", a[i], b[i], c[i], d[i]); |
105 |
130 |
106 return EXIT_SUCCESS; |
131 return EXIT_SUCCESS; |
107 } |
132 } |