mga / Parallele quick sort

#include <math.h> #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define INSERTION_SORT_THRESHOLD 50 #define BLOCKSIZE 256 #define min(a, b) ((a) < (b) ? (a) : (b)) #define swap(a, b) \ { \ a ^= b; \ b ^= a; \ a ^= b; \ } typedef struct { int *array; int left; int right; int depth; } quicksort_args; int max_threads; int current_threads = 1; pthread_mutex_t thread_lock = PTHREAD_MUTEX_INITIALIZER; // Insertion sort for small ranges void insert_sort(int *left, int *right) { for (int *pi = left + 1; pi <= right; pi++) { if (*pi < *left) swap(*pi, *left); } for (int *pi = left + 2; pi <= right; pi++) { int h = *pi; int *pj = pi - 1; while (h < *pj) { *(pj + 1) = *pj; pj--; } *(pj + 1) = h; } } // Median-of-three #define sort3fast(a, b, c) \ if (b < a) { \ if (c < a) { \ if (c < b) { \ swap(a, c); \ } else { \ int h = a; \ a = b; \ b = c; \ c = h; \ } \ } else { \ swap(a, b); \ } \ } else { \ if (c < b) { \ if (c < a) { \ int h = c; \ c = b; \ b = a; \ a = h; \ } else { \ swap(b, c); \ } \ } \ } // Hoare’s partition with median-of-three void partition(int *left0, int *right0, int **l1, int **r1, int **l2, int **r2) { int *mid = left0 + (right0 - left0) / 2; int piv = *mid; *mid = *(left0 + 1); sort3fast(*left0, piv, *right0); *(left0 + 1) = piv; int *left = left0 + 1; int *right = right0; while (1) { while (*++left < piv) ; while (*--right > piv) ; if (left >= right) break; swap(*left, *right); } *(left0 + 1) = *right; *right = piv; if (right < mid) { *l1 = left0; *r1 = right - 1; *l2 = right + 1; *r2 = right0; } else { *l1 = right + 1; *r1 = right0; *l2 = left0; *r2 = right - 1; } } // Recursive quicksort, parallelized void *parallel_quicksort(void *args) { quicksort_args *qargs = (quicksort_args *)args; int *array = qargs->array; int left = qargs->left; int right = qargs->right; int depth = qargs->depth; while (right - left >= INSERTION_SORT_THRESHOLD) { int *l, *r, *l2, *r2; partition(array + left, array + right, &l, &r, &l2, &r2); int l_idx = l - array; int r_idx = r - array; int l2_idx = l2 - array; int r2_idx = r2 - array; int spawn = 0; pthread_t thread; quicksort_args *right_args = malloc(sizeof(quicksort_args)); right_args->array = array; right_args->left = l2_idx; right_args->right = r2_idx; right_args->depth = depth + 1; pthread_mutex_lock(&thread_lock); if (current_threads < max_threads) { current_threads++; spawn = 1; } pthread_mutex_unlock(&thread_lock); if (spawn) { pthread_create(&thread, NULL, parallel_quicksort, right_args); } else { parallel_quicksort(right_args); free(right_args); } quicksort_args left_args = {array, l_idx, r_idx, depth + 1}; parallel_quicksort(&left_args); if (spawn) { pthread_join(thread, NULL); pthread_mutex_lock(&thread_lock); current_threads--; pthread_mutex_unlock(&thread_lock); free(right_args); } return NULL; } // small array — do insertion sort insert_sort(array + left, array + right); if (depth == 0) free(qargs); return NULL; } int get_named_arg(int argc, char *argv[], const char *name) { for (int i = 1; i < argc - 1; ++i) { if (strcmp(argv[i], name) == 0) { return atoi(argv[i + 1]); } } return -1; } int main(int argc, char **argv) { int power = get_named_arg(argc, argv, "--size"); max_threads = get_named_arg(argc, argv, "--threads"); if (power < 1 || max_threads < 1) { fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n", argv[0]); return EXIT_FAILURE; } int n = (int)pow(10, power); int *array = (int *)malloc(n * sizeof(int)); if (!array) { perror("malloc"); return EXIT_FAILURE; } srand(time(NULL)); for (int i = 0; i < n; i++) array[i] = rand(); quicksort_args *args = malloc(sizeof(quicksort_args)); args->array = array; args->left = 0; args->right = n - 1; args->depth = 0; parallel_quicksort(args); free(array); return 0; }