Login
mga

mga / Parallele bubble sort

Last active 3 months ago

Like 0
main.c Raw
1#include <math.h>
2#include <pthread.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <unistd.h>
7
8#define TRUE 1
9#define FALSE 0
10
11int *array_ptr;
12pthread_barrier_t barrier;
13
14typedef struct {
15 int thread_id;
16 int *arr;
17 int size;
18 int n_threads;
19} thread_args;
20
21void generateArray(int *array, int size) {
22 for (int i = 0; i < size; ++i) {
23 array[i] = rand() % 1000;
24 }
25}
26
27int verify(int *array, int size) {
28 for (int i = 0; i < size - 1; ++i) {
29 if (array[i] > array[i + 1]) {
30 return FALSE;
31 }
32 }
33 return TRUE;
34}
35
36void printArray(int *arr, int n) {
37 for (int i = 0; i < n; ++i) {
38 printf("%d ", arr[i]);
39 }
40 printf("\n");
41}
42
43void *parallel_bubble_sort(void *arg) {
44 thread_args *args = (thread_args *)arg;
45 int tid = args->thread_id;
46 int *arr = args->arr;
47 int n = args->size;
48 int n_threads = args->n_threads;
49
50 for (int step = 0; step < n; ++step) {
51 int start = (step % 2 == 0) ? 0 : 1;
52 for (int i = start + 2 * tid; i < n - 1; i += 2 * n_threads) {
53 if (arr[i] > arr[i + 1]) {
54 int tmp = arr[i];
55 arr[i] = arr[i + 1];
56 arr[i + 1] = tmp;
57 }
58 }
59 pthread_barrier_wait(&barrier);
60 }
61
62 return NULL;
63}
64
65// Argument parsing utility
66int get_named_arg(int argc, char *argv[], const char *name) {
67 for (int i = 1; i < argc - 1; ++i) {
68 if (strcmp(argv[i], name) == 0) {
69 return atoi(argv[i + 1]);
70 }
71 }
72 return -1;
73}
74
75int main(int argc, char *argv[]) {
76 int power = get_named_arg(argc, argv, "--size");
77 int n_threads = get_named_arg(argc, argv, "--threads");
78
79 if (power < 1 || n_threads < 1) {
80 fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n",
81 argv[0]);
82 return EXIT_FAILURE;
83 }
84
85 int n = (int)pow(10, power);
86
87 array_ptr = (int *)malloc(n * sizeof(int));
88 if (!array_ptr) {
89 perror("malloc");
90 return EXIT_FAILURE;
91 }
92
93 pthread_t *threads = malloc(n_threads * sizeof(pthread_t));
94 thread_args *args = malloc(n_threads * sizeof(thread_args));
95 if (!threads || !args) {
96 perror("malloc");
97 return EXIT_FAILURE;
98 }
99
100 generateArray(array_ptr, n);
101 pthread_barrier_init(&barrier, NULL, n_threads);
102
103 for (int i = 0; i < n_threads; ++i) {
104 args[i].thread_id = i;
105 args[i].arr = array_ptr;
106 args[i].size = n;
107 args[i].n_threads = n_threads;
108 pthread_create(&threads[i], NULL, parallel_bubble_sort, &args[i]);
109 }
110
111 for (int i = 0; i < n_threads; ++i) {
112 pthread_join(threads[i], NULL);
113 }
114
115 pthread_barrier_destroy(&barrier);
116
117 // Uncomment to see result
118 // printArray(array_ptr, n);
119
120 /*
121 if (verify(array_ptr, n))
122 printf("\nArray is sorted.\n");
123 else
124 printf("\nArray is NOT sorted.\n");
125 */
126
127 free(array_ptr);
128 free(threads);
129 free(args);
130
131 return 0;
132}
133