I have this project where I need to create an array, split it into two, and then sort each array using its own thread, then merge the two arrays back into a single array. Thankfully, the final array doesn't need to be sorted itself.
I wrote this code:
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
//Change length of main input array
const int arrLen = 20;
const int mid = arrLen/2;
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void *sort(void *arg){
int min_pos;
for(int a=0; a<arrLen-1; a ){
min_pos = a;
for(int b=a 1; b<arrLen; b ){
if(array[b] < array[min_pos]){
min_pos = b;
}
}
swap(&array[min_pos], &array[a]);
}
}
void printResult(int array[]){
for(int k=0; k<arrLen/2; k ){
printf("Num%d: %d\n", k, array[k]);
}
}
//Adds random values to each position in a given array
void arrayCreator(int array[]){
int random;
for(int i=0; i<arrLen; i ){
random = rand() % 100;
array[i] = random;
}
}
void main(){
printf("Program Initialized...\n");
int mainArray [arrLen], firstHalf[mid], secondHalf[mid], random;
time_t t;
srand((unsigned) time(&t));
//Populate mainArray
for(int i=0; i<arrLen; i ){
mainArray[i] = rand()0;
}
printf("Array created...\n");
//Split mainArray[] into two seperate arrays
for(int p=0; p<arrLen; p ){
if(p<mid){
firstHalf[p]=mainArray[p];
}
else{
secondHalf[p-mid]=mainArray[p];
}
}
pthread_t tid1;
pthread_t tid2;
pthread_create(&tid1, NULL, sort, (void*)firstHalf);
//pthread_create(&tid2, NULL, sort, secondHalf);
printResult(firstHalf);
//printResult(secondHalf);
}
How can I get the sort function to access my array?
CodePudding user response：
Simply assign arg to your array variable in order to convert from void * to int *.
void *sort(void *arg){
int min_pos;
int *array = arg;
for(int a=0; a<arrLen-1; a ){
min_pos = a;
for(int b=a 1; b<arrLen; b ){
if(array[b] < array[min_pos]){
min_pos = b;
}
}
swap(&array[min_pos], &array[a]);
}
}
CodePudding user response：
- First, I would look at the signature of the standard function
qsortand provide the same interface for yoursortfunction. I'd also rename it intobubble_sortsince it's doing bubble sorting. Your function would then look like this:void bubble_sort(void *ptr, size_t arrLen, size_t elem_size, int (*comp)(const void *, const void *)) { char *array = ptr; // to be able to do pointer arithmetic for (size_t a = 0; a < arrLen - 1; a ) { for (size_t b = a 1; b < arrLen; b ) { if (comp(array a * elem_size, array b * elem_size) > 0) { swap(array a * elem_size, array b * elem_size, elem_size); } } } }elem_sizeis the size of the elements you want to sort, which will be set tosizeof(int)later.compis a function taking twovoid*and returns anintwhere ...< 0means*a < *b> 0means*a > *b== 0means*a == *b
swapalso takes theelem_sizeparameter to be able to swap objects of any size. Implemented, it could look like this:void swap(void *a, void *b, size_t elem_size) { char tmp[elem_size]; memcpy(tmp, a, elem_size); memcpy(a, b, elem_size); memcpy(b, tmp, elem_size); }
Now, you can't start a thread by calling bubble_sort directly. A thread start routine only takes a single void* as an argument so we need some way of passing all the necessary arguments on. We can package them in a struct like this:
struct sort_thread_args {
pthread_t tid;
void *array;
size_t arrLen;
size_t elem_size;
int (*comp_func)(const void *, const void *);
};
void *sort_thread(void *arg) { // the thread start routine
struct sort_thread_args *ta = arg;
bubble_sort(ta->array, ta->arrLen, ta->elem_size, ta->comp_func);
return NULL;
}
As can be seen above, the struct contains all the necessary information to call bubble_sort the thread id, which I've stored there for convenience only. It's not needed by the thread itself.
The above functions are type agnostic so you can use these to sort any contiguous array, either by calling bubble_sort directly or in a thread.
Since you'll be using this to sort arrays of int, we need a comparison function for ints which does what was described above:
int comp_int(const void *va, const void *vb) {
const int *a = va;
const int *b = vb;
if (*a < *b) return -1;
if (*a > *b) return 1;
return 0;
}
Then for sorting half the array in one thread and the other half in another thread, I suggest that you don't copy the contents of mainArray to new arrays. Just leave the content in mainArray and tell each thread where to start sorting and how many elements it should sort.
Example:
#define Size(x) (sizeof(x) / sizeof *(x))
int main() {
srand((unsigned)time(NULL));
puts("Program Initialized...");
int arrLen = 35; // just an example to show that it handes uneven amounts too
int mainArray[arrLen];
// Populate mainArray
for (size_t i = 0; i < Size(mainArray); i ) {
mainArray[i] = rand() % 100;
}
puts("Array created...");
// print the created array
for (size_t i = 0; i < Size(mainArray); i) printf("- ", mainArray[i]);
putchar('\n');
puts("Running sorting threads...");
struct sort_thread_args ta[2]; // 2 for 2 threads
for (size_t i = 0; i < Size(ta); i) {
// element index for where this thread should start sorting:
size_t base = i * Size(mainArray) / Size(ta);
// prepare the arguments for this thread:
ta[i] = (struct sort_thread_args) {
.array = mainArray base, // points at the first element for this thread
.arrLen = (i 1) * Size(mainArray) / Size(ta) - base,
.elem_size = sizeof(int),
.comp_func = comp_int // the comparison function we made above
};
// and start the thread:
pthread_create(&ta[i].tid, NULL, sort_thread, &ta[i]);
}
puts("Joining threads");
for (size_t i = 0; i < Size(ta); i) {
pthread_join(ta[i].tid, NULL);
}
puts("Result:");
for (size_t i = 0; i < Size(mainArray); i) printf("- ", mainArray[i]);
putchar('\n');
}