sort.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Sun, 26 Jul 2009 18:14:15 +0200
changeset 102 b8ff193b1a01
parent 77 49e0babccb23
permissions -rw-r--r--
Property java.library.path i've found out how to set the library path correctly with java tools 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
/**
77
49e0babccb23 HEADER TAGS
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 74
diff changeset
     2
 * sort.c
49e0babccb23 HEADER TAGS
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 74
diff changeset
     3
 * Copyright (C) 2008 Markus Broeker
49e0babccb23 HEADER TAGS
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 74
diff changeset
     4
 *
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     5
 * Comparision of Sorting Algorithms
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     6
 */
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     7
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     8
#include <stdio.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     9
#include <stdlib.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    10
#include <string.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    11
#include <time.h>
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    12
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    13
#ifndef MAX
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    14
#define MAX 50000
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    15
#endif
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    16
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    17
unsigned long counter = 0;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    18
unsigned long iters = 0;
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
int compare (int *a, int *b)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    21
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    22
    iters++;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    23
    if (*a > *b) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    24
        counter++;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    25
        return 1;
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
    return 0;
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
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    30
void swap (int *v, int i, int j)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    31
{
74
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    32
    int old;
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    33
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    34
    if (i == j)
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    35
        return;
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    36
829976007e62 getrandom macro fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 73
diff changeset
    37
    old = v[i];
25
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
    v[i] = v[j];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
    v[j] = old;
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
void statistic (char *func)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    44
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    45
    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
    46
    counter = iters = 0;
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
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    49
/**
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    50
 * 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
    51
 */
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
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
    53
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    54
    int i, j;
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
    for (i = 1; i < n; i++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
        for (j = 0; j < n; j++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    58
            if (compare_func (&v[j], &v[i])) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    59
                swap (v, i, j);
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
        }
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
    statistic ("Lazy");
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
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
 * 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
    68
 */
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    69
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
    70
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    71
    int i, j;
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    72
70
ded389a5dc2a Profiling support added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 48
diff changeset
    73
    for (i = (n - 1); i > 0; i--) {
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    74
        for (j = 1; j <= i; j++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    75
            if (compare (&v[j - 1], &v[j])) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    76
                swap (v, j - 1, j);
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    77
            }
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
    }
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    80
    statistic ("Linear");
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
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
 * 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
    85
 */
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    86
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
    87
{
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    88
    int i;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    89
    int swapped;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    90
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    91
    do {
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    92
        swapped = 0;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    93
        for (i = 1; i < n; i++) {
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    94
            if (compare (&v[i - 1], &v[i])) {
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    95
                swap (v, i, i - 1);
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    96
                swapped = 1;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    97
            }
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    98
        }
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
    99
        n--;
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   100
    } while (swapped && n >= 1);
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   101
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   102
    statistic ("Bubble");
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   103
}
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   104
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   105
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
   106
{
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   107
    int i, j, pivot;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   108
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   109
    i = left;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   110
    j = right - 1;
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
    pivot = v[right];
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   113
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   114
    do {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   115
        while (v[i] <= pivot && i < right) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   116
            iters++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   117
            i++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   118
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   119
        while (v[j] >= pivot && j > left) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   120
            iters++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   121
            j--;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   122
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   123
        if (i < j) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   124
            counter++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   125
            swap (v, i, j);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   126
        }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   127
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   128
        if (v[i] > pivot) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   129
            counter++;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   130
            swap (v, i, right);
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
    } while (i < j);
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
    return i;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   135
}
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
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
   138
{
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   139
    int divisor;
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   140
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   141
    if (left < right) {
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   142
        divisor = divide (v, left, right);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   143
        quicksort (v, left, divisor - 1);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   144
        quicksort (v, divisor + 1, right);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   145
    }
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   146
}
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   147
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   148
int main (int argc, char **argv)
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   149
{
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   150
    int a[MAX];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   151
    int b[MAX];
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   152
    int c[MAX];
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   153
    int d[MAX];
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   154
    int e[MAX];
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 25
diff changeset
   155
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   156
    int i;
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
    srand (time (NULL));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   159
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   160
    for (i = 0; i < MAX; i++) {
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   161
        a[i] = (int)((float)MAX * rand () / (RAND_MAX + 1.0));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   162
    }
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   163
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   164
    memcpy (b, a, sizeof (a));
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   165
    memcpy (c, a, sizeof (a));
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   166
    memcpy (d, a, sizeof (a));
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   167
    memcpy (e, a, sizeof (a));
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   168
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   169
    lazysort (a, MAX, &compare);
72
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   170
    linearsort (b, MAX, &compare);
4103c76d5bf2 sort.c: bubblesort fixed
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 70
diff changeset
   171
    bubblesort (c, MAX, &compare);
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   172
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   173
    quicksort (d, 0, MAX - 1);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   174
    statistic ("mquick");
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   175
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   176
    qsort (e, MAX, sizeof (int), (void *)&compare);
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   177
    statistic ("gquick");
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   178
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   179
    printf ("PRESS <RETURN> to CONTINUE");
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   180
    while (getchar () != '\n');
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   181
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   182
    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
   183
    for (i = 0; i < MAX; i++)
73
d0578510aea1 Changelog: Makefile and sort.c
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 72
diff changeset
   184
        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
   185
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
   186
    return EXIT_SUCCESS;
25
6cf883f9c506 sort demo added
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   187
}