1 /**

     2  * Comparision of Sorting Algorithms

     3  * Copyright (C) 2008 Markus Broeker

     4  */

     5 

     6 #include <stdio.h>

     7 #include <stdlib.h>

     8 #include <string.h>

     9 #include <time.h>

    10 

    11 #ifndef MAX

    12 #define MAX 50000

    13 #endif

    14 

    15 unsigned long counter = 0;

    16 unsigned long iters = 0;

    17 

    18 int compare (int *a, int *b)

    19 {

    20     iters++;

    21     if (*a > *b) {

    22         counter++;

    23         return 1;

    24     }

    25     return 0;

    26 }

    27 

    28 void swap (int *v, int i, int j)

    29 {

    30     int old = v[i];

    31 

    32     v[i] = v[j];

    33     v[j] = old;

    34 }

    35 

    36 void statistic (char *func)

    37 {

    38     printf ("%8s finished after %10lu swaps and %10lu Iterations.\n", func, counter, iters);

    39     counter = iters = 0;

    40 }

    41 

    42 /**

    43  * Laufzeitverhalten: n*(n-1) Durchläufe zum Sortieren von n Elementen...

    44  */

    45 void lazysort (int *v, int n, int (*compare_func) (int *, int *))

    46 {

    47     int i, j;

    48 

    49     for (i = 1; i < n; i++) {

    50         for (j = 0; j < n; j++) {

    51             if (compare_func (&v[j], &v[i])) {

    52                 swap (v, i, j);

    53             }

    54         }

    55     }

    56     statistic ("Lazy");

    57 }

    58 

    59 /**

    60  * Laufzeitverhalten: (1/2)*n*(n-1) Durchläufe zum Sortieren von n Elementen...

    61  */

    62 void bubblesort (int *v, int n, int (*compare) (int *, int *))

    63 {

    64     int i, j;

    65 

    66     for (i = (n - 1); i >= 0; i--) {

    67         for (j = 1; j <= i; j++) {

    68             if (compare (&v[j - 1], &v[j])) {

    69                 swap (v, j - 1, j);

    70             }

    71         }

    72     }

    73     statistic ("Bubble");

    74 }

    75 

    76 int main (int argc, char **argv)

    77 {

    78     int a[MAX];

    79     int b[MAX];

    80     int c[MAX];

    81     int i;

    82 

    83     srand (time (NULL));

    84 

    85     for (i = 0; i < MAX; i++) {

    86         a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0));

    87     }

    88 

    89     memcpy (b, a, sizeof (a));

    90     memcpy (c, a, sizeof (a));

    91 

    92     lazysort (a, MAX, &compare);

    93     bubblesort (b, MAX, &compare);

    94 

    95     qsort (c, MAX, sizeof (int), (void *)&compare);

    96     statistic ("Quick");

    97 

    98     printf ("PRESS <RETURN> to CONTINUE");

    99     while (getchar () != 10);

   100     printf ("%2c %2c %2c\n--------\n", 'L', 'B', 'Q');

   101 

   102     for (i = 0; i < MAX; i++)

   103         printf ("%2d %2d %2d\n", a[i], b[i], c[i]);

   104 

   105     return 0;

   106 }