sort.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Thu, 16 Apr 2009 12:50:39 +0200
changeset 76 c46968bddef5
parent 74 829976007e62
child 77 49e0babccb23
permissions -rw-r--r--
A nice system daemon... Daemon monitors /proc/meminfo every 60 seconds... 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;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    16
unsigned long iters = 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    17
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    18
int compare (int *a, int *b)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    19
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    20
    iters++;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    21
    if (*a > *b) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    22
        counter++;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    23
        return 1;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    24
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    25
    return 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    26
}
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
void swap (int *v, int i, int j)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    29
{
74
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    30
    int old;
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    31
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    32
    if (i == j)
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    33
        return;
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    34
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    35
    old = v[i];
25
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
    v[i] = v[j];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    38
    v[j] = old;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    39
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    41
void statistic (char *func)
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
    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
    44
    counter = iters = 0;
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
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    47
/**
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    48
 * Laufzeitverhalten: n^2-n Durchläufe zum Sortieren von n Elementen...
25
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
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
    51
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
    int i, j;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    53
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    54
    for (i = 1; i < n; i++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    55
        for (j = 0; j < n; j++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    56
            if (compare_func (&v[j], &v[i])) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
                swap (v, i, j);
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
    statistic ("Lazy");
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
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    64
/**
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    65
 * Laufzeitverhalten: (1/2)*n^2-n Durchläufe zum Sortieren von n Elementen...
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    66
 */
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    67
void linearsort (int *v, int n, int (*compare) (int *, int *))
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    68
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    69
    int i, j;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    70
70
ded389a5dc2a Profiling support added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 48
diff changeset
    71
    for (i = (n - 1); i > 0; i--) {
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    72
        for (j = 1; j <= i; j++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    73
            if (compare (&v[j - 1], &v[j])) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    74
                swap (v, j - 1, j);
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
    }
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    78
    statistic ("Linear");
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    79
}
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    80
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    81
/**
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    82
 * Laufzeitverhalten: ~(1/{2|4})*n^2-n Durchläufe zum Sortieren...
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    83
 */
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    84
void bubblesort (int *v, int n, int (*compare) (int *, int *))
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    85
{
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    86
    int i;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    87
    int swapped;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    88
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    89
    do {
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    90
        swapped = 0;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    91
        for (i = 1; i < n; i++) {
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    92
            if (compare (&v[i - 1], &v[i])) {
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    93
                swap (v, i, i - 1);
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    94
                swapped = 1;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    95
            }
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    96
        }
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    97
        n--;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    98
    } while (swapped && n >= 1);
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    99
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   100
    statistic ("Bubble");
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
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   103
static int divide (int *v, int left, int right)
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   104
{
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   105
    int i, j, pivot;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   106
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   107
    i = left;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   108
    j = right - 1;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   109
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   110
    pivot = v[right];
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   111
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   112
    do {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   113
        while (v[i] <= pivot && i < right) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   114
            iters++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   115
            i++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   116
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   117
        while (v[j] >= pivot && j > left) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   118
            iters++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   119
            j--;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   120
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   121
        if (i < j) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   122
            counter++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   123
            swap (v, i, j);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   124
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   125
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   126
        if (v[i] > pivot) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   127
            counter++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   128
            swap (v, i, right);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   129
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   130
    } while (i < j);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   131
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   132
    return i;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   133
}
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   134
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   135
void quicksort (int *v, int left, int right)
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   136
{
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   137
    int divisor;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   138
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   139
    if (left < right) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   140
        divisor = divide (v, left, right);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   141
        quicksort (v, left, divisor - 1);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   142
        quicksort (v, divisor + 1, right);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   143
    }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   144
}
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   145
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   146
int main (int argc, char **argv)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   147
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   148
    int a[MAX];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   149
    int b[MAX];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   150
    int c[MAX];
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   151
    int d[MAX];
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   152
    int e[MAX];
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 25
diff changeset
   153
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   154
    int i;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   155
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   156
    srand (time (NULL));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   157
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   158
    for (i = 0; i < MAX; i++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   159
        a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   160
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   161
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   162
    memcpy (b, a, sizeof (a));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   163
    memcpy (c, a, sizeof (a));
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   164
    memcpy (d, a, sizeof (a));
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   165
    memcpy (e, a, sizeof (a));
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   166
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   167
    lazysort (a, MAX, &compare);
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   168
    linearsort (b, MAX, &compare);
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   169
    bubblesort (c, MAX, &compare);
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   170
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   171
    quicksort (d, 0, MAX - 1);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   172
    statistic ("mquick");
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   173
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   174
    qsort (e, MAX, sizeof (int), (void *)&compare);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   175
    statistic ("gquick");
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   176
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   177
    printf ("PRESS <RETURN> to CONTINUE");
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   178
    while (getchar () != '\n');
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   179
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   180
    printf ("%6c %6c %6c %6c %6c\n----------------------------------\n", 'L', 'N', 'B', 'M', 'G');
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   181
    for (i = 0; i < MAX; i++)
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   182
        printf ("%6d %6d %6d %6d %6d\n", a[i], b[i], c[i], d[i], e[i]);
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   183
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
   184
    return EXIT_SUCCESS;
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   185
}