gistfile1.txt

100000,4498507,3303010,648466,16
200000,8362325,6241487,1600060,17
300000,14234516,9815716,2576244,18
400000,20917134,15040464,3536045,18
500000,27302971,18864431,4210794,18
600000,34065834,24098987,5387591,19
700000,41003115,30249966,6298501,19
800000,48902149,35815841,7190792,19
900000,59714105,41751355,8217691,19
1000000,63407397,47906822,9090613,19

sort.c

#include "unistd.h"
#include "stdio.h"
#include "time.h"
#include "string.h"
#include "stdlib.h"

int random_num(int min, int max) {
    return (rand() / ((double)RAND_MAX + 1)) * (max-min+1) + min;
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

size_t partition(int array[], size_t l, size_t h) {
    // element rozdzielny jest tutaj ostatnim elementem fragmentu tablicy!
    int pivot = array[h];
    size_t i = l, j;
 
    for(j = l; j < h; j++) {
        if(array[j] <= pivot) {
            swap(&array[i], &array[j]);
            i++;
        }
    }
    swap(&array[i], &array[h]);
    return i;
}

void quicksort_last(int array[], size_t len) {
    size_t stack[len], l = 0, h = len - 1;
    int top = -1;

    for(;;) {
        size_t p = partition(array, l, h);
        if(p != 0 && p - 1 > l) {
            stack[++top] = l;
            stack[++top] = p - 1;
        }
        if(p + 1 < h) {
            stack[++top] = p + 1;
            stack[++top] = h;
        }

        if(top < 1) {
            break;
        }

        h = stack[top--];
        l = stack[top--];
    }
}

void quicksort_rand(int array[], size_t len) {
    size_t stack[len], l = 0, h = len - 1;
    int top = -1;

    for(;;) {
        size_t pivot_idx = random_num(l, h);
        swap(&array[pivot_idx], &array[h]);
        size_t p = partition(array, l, h);
        if(p != 0 && p - 1 > l) {
            stack[++top] = l;
            stack[++top] = p - 1;
        }
        if(p + 1 < h) {
            stack[++top] = p + 1;
            stack[++top] = h;
        }

        if(top < 1) {
            break;
        }

        h = stack[top--];
        l = stack[top--];
    }
}

void quicksort_rec_last(int array[], int left, int right) {
    if(left < right) {
        int pivot = partition(array, left, right);
        quicksort_rec_last(array, left, pivot-1);
        quicksort_rec_last(array, pivot+1, right);
    }
}

void quicksort_rec_rand(int array[], int left, int right) {
    if(left < right) {
        size_t pivot_idx = random_num(left, right);
        swap(&array[pivot_idx], &array[right]);
        int pivot = partition(array, left, right);
        quicksort_rec_rand(array, left, pivot-1);
        quicksort_rec_rand(array, pivot+1, right);
    }
}

// HEAPSORT
 
void siftDown(int array[], int start, int end) {
    int root = start;
 
    while(root*2+1 < end) {
        int child = 2 * root + 1;
        if(child + 1 < end && array[child] < array[child+1]) {
            child += 1;
        }

        if (array[root] < array[child]) {
            swap(&array[child], &array[root]);
            root = child;
        } else {
            return;
        }
    }
}

void heapsort(int array[], int len) {
    int start, end;
 
    for (start = (len-2)/2; start >= 0; start--) {
        siftDown(array, start, len);
    }
 
    for (end = len - 1; end > 0; end--) {
        swap(&array[end], &array[0]);
        siftDown(array, 0, end);
    }
}

int main(int argc, char const *argv[]) {
    srand(time(NULL));
    int n = 100000;
    int *losowy = malloc(n * sizeof(int));
    int *rosnacy = malloc(n * sizeof(int));
    int *malejacy = malloc(n * sizeof(int));
    int *staly = malloc(n * sizeof(int));
    int *a_ksztalt = malloc(n * sizeof(int));
    int *tab[5] = {losowy, rosnacy, malejacy, staly, a_ksztalt};
    int *tab_tmp[5] = {malloc(n * sizeof(int)),
                       malloc(n * sizeof(int)),
                       malloc(n * sizeof(int)),
                       malloc(n * sizeof(int)),
                       malloc(n * sizeof(int))};

    for(int i=0; i<n; i++) {
        losowy[i] = random_num(0, 1000);
        rosnacy[i] = i * 3;
        malejacy[i] = (n - i) * 3;
        staly[i] = 42;
    }

    int start = 5000, krok = 5000;

    for(int rozmiar = start; rozmiar <= n; rozmiar += krok) {
        memcpy(a_ksztalt, rosnacy, rozmiar/2*sizeof(int));
        memcpy(&a_ksztalt[rozmiar/2], malejacy, rozmiar/2*sizeof(int));
        double wynik[5];
        struct timespec tstart={0,0}, tend={0,0};
        printf("%d", rozmiar);
        for(int i=0; i<5; i++) {
            memcpy(tab_tmp[i], tab[i], rozmiar*sizeof(int));
            clock_gettime(CLOCK_MONOTONIC, &tstart);
            heapsort(tab_tmp[i], rozmiar);
            clock_gettime(CLOCK_MONOTONIC, &tend);
            wynik[i] = ((double)tend.tv_sec * 1.0e3 + 1.0e-6*tend.tv_nsec) - 
                       ((double)tstart.tv_sec * 1.0e3 + 1.0e-6*tstart.tv_nsec);
            printf(",%.6f", wynik[i]);
            int last = -1;
            for (int j = 0; j < rozmiar; ++j)
            {
                if(last > tab_tmp[i][j]) abort();
                last = tab_tmp[i][j];
            }
        }
        printf("\n");
    }
    return 0;
}