In the following I'm trying to sort an array with multiple threads using pthreads. The idea is to split the array and give each thread one part. shell_sort does it in serial while in my parallel try I call it by each thread.
The multithread version did not match the serial result (which I think is correct), so I believe there is an issue in my parrallel solution which is where I would like to ask for help.
Here is main.c which is my parallel try:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <pthread.h>
typedef struct {
double *array;
int size;
} data_s;
double *gen_rand(int size, double min, double max) {
srand(time(0));
double *array = malloc(size*sizeof(double));
for(int i = 0; i < size; i++) {
double v = min + rand() / (RAND_MAX/(max-min));
array[i] = floor(v*10)/10;
}
return array;
}
void print(double *array, int size) {
for(int i = 0; i < size; i++)
printf("%.2f ", array[i]);
printf("\n");
}
void swap(double *a, double *b) {
double tmp = *a;
*a = *b;
*b = tmp;
}
void shell_sort(double *array, int size) {
printf("ssort serial\n");
int h = floor(size/2);
while(h >= 1) {
for(int i = h; i < size; i++)
for(int j = i; j >= h && array[j] < array[j-h]; j-=h)
swap(&array[j], &array[j-h]);
h = floor(h/2);
}
}
void *ssort_thread(void *arg) {
printf("ssort parallel\n");
data_s data = *(data_s*)arg;
shell_sort(data.array, data.size);
return 0;
}
void ssort_parallel(double *array, int size, int part) {
int threads = size/part;
pthread_t thread[threads];
for (int i = 0; i < threads; i++) {
print(array+i*part, part);
pthread_create(&thread[i], NULL,
ssort_thread, &(data_s){array+i*part, part});
}
for (int i = 0; i < threads; i++)
pthread_join(thread[i], NULL);
}
int main(int argc, char **argv) {
int array_size = 10;
double *array = gen_rand(array_size, 0, 99);
print(array, array_size);
int threads = 2;
int part = array_size/threads;
ssort_parallel(array, array_size, part);
print(array, array_size);
}
I achieve a serial result by modifying ssort_parallel to:
void ssort_parallel(double *array, int size, int part) {
int threads = size/part;
pthread_t thread[threads];
for (int i = 0; i < threads; i++) {
print(array+i*part, part);
shell_sort(array+i*part, part);
}
}
Just would like to note: Expected result is not full array sorted. Instead, left part and right part should be sorted.
This is what I got for parallel:
$ ./main
38.60 11.10 22.00 57.00 31.50 89.10 36.00 79.50 3.80 18.10
38.60 11.10 22.00 57.00 31.50
89.10 36.00 79.50 3.80 18.10
ssort parallel
ssort parallel
ssort serial
ssort serial
38.60 11.10 22.00 57.00 31.50 3.80 18.10 36.00 79.50 89.10
And what I got for serial:
$ ./main
39.10 42.10 98.20 42.40 30.90 88.50 9.40 54.30 9.30 35.40
39.10 42.10 98.20 42.40 30.90
ssort serial
88.50 9.40 54.30 9.30 35.40
ssort serial
30.90 39.10 42.10 42.40 98.20 9.30 9.40 35.40 54.30 88.50
My feeling is that most of the times right side is correct in parallel.
