Question

Implement a parallel version of the BubbleSort algorithm. Write C++ code in directory bubblesort/ in bubblesort.cpp. Remember to set thread count and granularity using the setNbThread() and setGranularity() functions provided in the omploop.hpp . Output the time it took on stderr.

Answer 1

To implement a parallel version of the BubbleSort algorithm in C++, you can use the OpenMP library. Here's an example of how you can implement a parallel BubbleSort algorithm using OpenMP in C++. After the sorting is complete, we output the time it took using std::cerr.

Step-by-step explanation:

To implement a parallel version of the BubbleSort algorithm in C++, you can use the OpenMP library. OpenMP provides the setNbThread() and setGranularity() functions that allow you to control the number of threads and the size of the work chunks. Here's an example of how you can implement a parallel BubbleSort algorithm:

#include <iostream>
#include <omp.h>

void bubbleSort(int arr[], int n) {
int i, j;
#pragma omp parallel for
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);

omp_set_num_threads(4); // Set the number of threads
bubbleSort(arr, n);

std::cerr << "Time took: " << omp_get_wtime() << std::endl;

return 0;
}

In this code, we use the #pragma omp parallel for directive to parallelize the outer loop of the BubbleSort algorithm. We set the number of threads to 4 using omp_set_num_threads(). After the sorting is complete, we output the time it took using std::cerr.