두 개의 쓰레드를 활용한 병합정렬(merge sorting)

#include <stdio.h>

#include <pthread.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>

#include <sys/time.h>

#define CHECK_END -1

static int *array = NULL;

static pthread_t tid[2];

static void div_array(int *, int, int, unsigned int);

static void merge_sort(int *, unsigned int);

void *left_sort(void *size)

{

int s = *((int *)size);

int middle = s/2;

div_array(array, 0, middle, (unsigned int)tid[0]);

}

void *right_sort(void *size)

{

int s = *((int *)size);

int middle = s/2;

div_array(array, middle + 1, s, (unsigned int)tid[1]);

}

static void init_array(int size)

{

int count = 0;

array = (int*)malloc(sizeof(int) * size);

for(count = 0 ; count < size ; count ++)

{

array[count] = rand()%size + 1;

}

}

static void display_array(int size)

{

int count = 0;

for(count = 0 ; count < size ; count ++)

{

printf("%d", array[count]);

if(count + 1 < size)

printf(", ");

else

printf(" END\n");

}

}

static void merge(int *arr, int start, int middle, int end, unsigned int tid)

{

int *arr_left, *arr_right;

int left = 0, right = 0;

int count = 0;

// printf("%u is working!\n", tid);

arr_left = (int*)malloc(sizeof(int) * (middle - start + 2));

arr_right = (int*)malloc(sizeof(int) * (end - middle + 1));

for(count = 0 ; count <= middle - start ; count ++)

{

arr_left[count] = arr[start + count];

}

arr_left[count] = CHECK_END;

for(count = 0 ; count < end - middle ; count ++)

{

arr_right[count] = arr[middle + count + 1];

}

arr_right[count] = CHECK_END;

for(count = start ; count <= end ; count ++)

{

if((arr_left[left] == CHECK_END || arr_left[left] > arr_right[right])

&& arr_right[right] != CHECK_END)

{

arr[count] = arr_right[right ++];

}

else

arr[count] = arr_left[left ++]; 

}

free(arr_left);

free(arr_right);

}

static void div_array(int *arr, int start, int end, unsigned int tid)

{

int middle = (start + end) / 2;

if(start < end)

{

div_array(arr, start, middle, tid);

div_array(arr, middle+1, end, tid);

merge(arr, start, middle, end, tid);

}

}

static void sort_merge(int size)

{

size = size - 1;

pthread_create(&tid[0], NULL,  &left_sort, &size);

pthread_create(&tid[1], NULL,  &right_sort, &size);

pthread_join(tid[0], NULL);

pthread_join(tid[1], NULL);

merge(array, 0, size/2, size, NULL);

}

int main(void)

{

srand(time(0));

struct timeval btime, atime;

long sec, msec;

int size = 0;

printf("input size of array : ");

scanf("%d", &size);

init_array(size);

gettimeofday(&btime, NULL);

sort_merge(size);

gettimeofday(&atime, NULL);

sec = atime.tv_sec - btime.tv_sec;

msec = (sec * 1000) + ((atime.tv_usec - btime.tv_usec) / 1000);

printf("finished! %ldmsec.\n", msec);

return 0;

}