Praktikum3_13513037

bucket_sort.c

+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <omp.h>
+
+int *create_rand_nums(int num_elements) {
+    int *rand_nums = malloc(sizeof(int) * num_elements);
+    int i;
+    for (i = 0; i < num_elements; i++) {
+        rand_nums[i] = rand() % num_elements;
+    }
+    return rand_nums;
+}
+
+int compare(const void *pa, const void *pb) {
+    int a = *(const int*)pa;
+    int b = *(const int*)pb;
+    if (a < b) return -1;
+    else if (a > b) return 1;
+    else return 0;
+}
+
+// bubble sort biar keliatan bedanya
+void sort(int *arr, int n) {
+    int i, j;
+    for (i = 0; i < n-1; i++) {
+        for (j = i + 1; j < n; ++j) {
+            if (arr[i] > arr[j]) {
+                int temp = arr[i];
+                arr[i] = arr[j];
+                arr[j] = temp;
+            }
+        }
+    }
+    // qsort(arr, n, sizeof(int), compare);
+}
+
+void bucket_sort(int min, int range, int num_elements, int *array, int *size_array, int **thread_array) {
+    int my_rank = omp_get_thread_num();
+    int i;
+    int lower_bound = min + (my_rank * range);
+    int upper_bound = lower_bound + range;
+    int index = 0;
+    for (i = 0; i < num_elements; ++i) {
+        if (array[i] >= lower_bound && array[i] < upper_bound)
+            thread_array[my_rank][index++] = array[i];
+    }
+    size_array[my_rank] = index;
+    sort(thread_array[my_rank], index);
+}
+
+int main(int argc, char* argv[]) {
+    if (argc != 3 && argc != 4) {
+        fprintf(stderr, "usage: %s <number of threads> <number of array> [-p]\n", argv[0]);
+        exit(0);
+    }
+    srand(time(NULL));
+
+    int thread_count = strtol(argv[1], NULL, 10);
+    int num_elements = strtol(argv[2], NULL, 10);
+
+    int i, j;
+
+    int *array = create_rand_nums(num_elements);
+    int *size_array = malloc(thread_count * sizeof(int));
+    int **thread_array = malloc(thread_count * sizeof(int*));
+    for (i = 0; i < thread_count; ++i)
+        thread_array[i] = malloc(num_elements * sizeof(int));
+
+    const int INF = 1e9;
+    int max = -INF;
+    int min = INF;
+    for (i = 0; i < num_elements; ++i) {
+        if (array[i] > max) max = array[i];
+        if (array[i] < min) min = array[i];
+    }
+    int range = (max-min)/thread_count + 1;
+    double start_time = omp_get_wtime();
+
+    #pragma omp parallel num_threads(thread_count)
+    {
+        bucket_sort(min, range, num_elements, array, size_array, thread_array);
+    }
+
+    int *sorted_array = malloc(num_elements * sizeof(int));
+    int index = 0;
+    for (i = 0; i < thread_count; ++i) {
+        for (j = 0; j < size_array[i]; ++j) {
+            sorted_array[index++] = thread_array[i][j];
+        }
+    }
+    double elapsed_time = omp_get_wtime() - start_time;
+
+    if (argc == 4) {
+        for (i = 0; i < index; ++i)
+            printf("%d ", sorted_array[i]);
+        printf("\n");
+    }
+    printf("Processed N = %d, M = %d. Elapsed time = %.3fs\n", thread_count, num_elements, elapsed_time);
+
+    free(array);
+    free(size_array);
+    for (i = 0; i < thread_count; ++i)
+        free(thread_array[i]);
+    free(thread_array);
+    free(sorted_array);
+
+    return 0;
+}