Academic example of mergesort implementation in C (non-parallel and parallel version) with sample python ctypes bindings.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

117 lines
2.6 KiB

#include "ms.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <errno.h>
struct timespec timespecdiff(struct timespec start, struct timespec end)
{
struct timespec temp;
if ((end.tv_nsec - start.tv_nsec) < 0) {
temp.tv_sec = end.tv_sec - start.tv_sec - 1;
temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec - start.tv_sec;
temp.tv_nsec = end.tv_nsec - start.tv_nsec;
}
return temp;
}
void shuffle(int foo[], size_t len)
{
int i;
int x;
int t;
for (i = 0; i < len; ++i) {
x = random() % len;
t = foo[x];
foo[x] = foo[i];
foo[i] = t;
}
}
int check_arr(int foo[], size_t len)
{
int i;
for (i = 0; i < len; ++i) {
if (foo[i] != i) {
return 0;
}
}
return 1;
}
int main(int argc, char **argv)
{
int i;
int *foo;
int len;
struct timespec start, end;
struct timespec diff;
long diffms;
int x;
int forklimitsz;
len = 50000001;
forklimitsz = 3;
foo = (int *) malloc(sizeof(int *) * len);
if (foo == NULL) {
fprintf(stderr, "Not enough memory\n");
exit(1);
}
for (i = 0; i < len; ++i) {
foo[i] = i;
}
srandom(time(NULL));
printf("arr len: %d\n", len);
for (x = 0; x < 2; ++x) {
if (x == 0) {
printf("linear\n");
} else {
printf("parallel\n");
}
shuffle(foo, len);
if (len <= 100) {
printf("sorting arr: \n");
for (i = 0; i < len; ++i) {
printf(" %d", foo[i]);
}
printf("\n");
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
if (x == 0) {
mymergesort(foo, len);
} else {
if (mymergesortp(foo, len, forklimitsz) < 0) {
perror("mergesortp");
}
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
if (len <= 100) {
printf("sorted arr: \n");
for (i = 0; i < len; ++i) {
printf(" %d", foo[i]);
}
printf("\n");
}
if (check_arr(foo, len) == 0) {
printf("ERROR in sort\n");
} else {
printf("sort OK\n");
diff = timespecdiff(start, end);
diffms = diff.tv_sec * 1000 + diff.tv_nsec / 1000000;
printf("duration: %lds %ldns\n\t%ldms\n", diff.tv_sec, diff.tv_nsec, diffms);
}
}
free(foo);
return 0;
}