sort.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Thu, 16 Apr 2009 12:47:18 +0200
changeset 28 54addf5893ef
parent 27 81a574d60c15
child 29 7abf6146898e
permissions -rw-r--r--
cstdlib declares EXIT_SUCCESS and EXIT_FAILURE in c++ committer: Markus Bröker <mbroeker@largo.homelinux.org>
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     1
/**
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     2
 * Comparision of Sorting Algorithms
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     3
 * Copyright (C) 2008 Markus Broeker
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     4
 */
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     5
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     6
#include <stdio.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     7
#include <stdlib.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     8
#include <string.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     9
#include <time.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    10
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    11
#ifndef MAX
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    12
#define MAX 50000
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    13
#endif
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    14
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    15
unsigned long counter = 0;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 25
diff changeset
    16
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    17
unsigned long iters = 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    18
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    19
int compare (int *a, int *b)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    20
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    21
    iters++;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    22
    if (*a > *b) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    23
        counter++;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    24
        return 1;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    25
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    26
    return 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    27
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    28
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    29
void swap (int *v, int i, int j)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    30
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    31
    int old = v[i];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    32
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    33
    v[i] = v[j];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    34
    v[j] = old;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    35
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    36
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    37
void statistic (char *func)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    38
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    39
    printf ("%8s finished after %10lu swaps and %10lu Iterations.\n", func, counter, iters);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
    counter = iters = 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    41
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    42
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    43
/**
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    44
 * Laufzeitverhalten: n*(n-1) Durchläufe zum Sortieren von n Elementen...
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    45
 */
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    46
void lazysort (int *v, int n, int (*compare_func) (int *, int *))
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    47
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    48
    int i, j;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    49
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    50
    for (i = 1; i < n; i++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    51
        for (j = 0; j < n; j++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
            if (compare_func (&v[j], &v[i])) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    53
                swap (v, i, j);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    54
            }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    55
        }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    56
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
    statistic ("Lazy");
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    58
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    59
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    60
/**
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    61
 * Laufzeitverhalten: (1/2)*n*(n-1) Durchläufe zum Sortieren von n Elementen...
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    62
 */
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    63
void bubblesort (int *v, int n, int (*compare) (int *, int *))
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    64
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    65
    int i, j;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    66
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    67
    for (i = (n - 1); i >= 0; i--) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    68
        for (j = 1; j <= i; j++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    69
            if (compare (&v[j - 1], &v[j])) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    70
                swap (v, j - 1, j);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    71
            }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    72
        }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    73
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    74
    statistic ("Bubble");
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    75
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    76
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    77
int main (int argc, char **argv)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    78
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    79
    int a[MAX];
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 25
diff changeset
    80
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    81
    int b[MAX];
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 25
diff changeset
    82
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    83
    int c[MAX];
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 25
diff changeset
    84
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    85
    int i;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    86
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    87
    srand (time (NULL));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    88
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    89
    for (i = 0; i < MAX; i++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    90
        a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    91
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    92
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    93
    memcpy (b, a, sizeof (a));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    94
    memcpy (c, a, sizeof (a));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    95
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    96
    lazysort (a, MAX, &compare);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    97
    bubblesort (b, MAX, &compare);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    98
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    99
    qsort (c, MAX, sizeof (int), (void *)&compare);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   100
    statistic ("Quick");
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   101
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   102
    printf ("PRESS <RETURN> to CONTINUE");
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   103
    while (getchar () != 10);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   104
    printf ("%2c %2c %2c\n--------\n", 'L', 'B', 'Q');
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   105
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   106
    for (i = 0; i < MAX; i++)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   107
        printf ("%2d %2d %2d\n", a[i], b[i], c[i]);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   108
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   109
    return 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   110
}