Hpc 02 bubble and merge:
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <omp.h>
using namespace std;
// Sequential Bubble Sort
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
// Parallel Bubble Sort using Odd-Even Transposition
void parallelBubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++) {
#pragma omp parallel for
for (int j = (i % 2); j < n - 1; j += 2) {
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
// Sequential Merge Sort
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Parallel Merge Sort using OpenMP
void parallelMergeSort(vector<int>& arr, int l, int r, int depth = 0) {
if (l < r) {
int m = l + (r - l) / 2;
if (depth < 4) { // limit depth to avoid oversubscription
#pragma omp parallel sections
{
#pragma omp section
parallelMergeSort(arr, l, m, depth + 1);
#pragma omp section
parallelMergeSort(arr, m + 1, r, depth + 1);
}
} else {
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
}
merge(arr, l, m, r);
}
}
int main() {
int n;
cout << "Enter size of array: ";
cin >> n;
vector<int> arr(n);
srand(time(0));
for (int i = 0; i < n; i++)
arr[i] = rand() % 10000;
// Sequential Bubble Sort
vector<int> b1 = arr;
double start = omp_get_wtime();
bubbleSort(b1);
double end = omp_get_wtime();
cout << "Sequential Bubble Sort time: " << (end - start) << " seconds\n";
// Parallel Bubble Sort
vector<int> b2 = arr;
start = omp_get_wtime();
parallelBubbleSort(b2);
end = omp_get_wtime();
cout << "Parallel Bubble Sort time: " << (end - start) << " seconds\n";
// Sequential Merge Sort
vector<int> m1 = arr;
start = omp_get_wtime();
mergeSort(m1, 0, n - 1);
end = omp_get_wtime();
cout << "Sequential Merge Sort time: " << (end - start) << " seconds\n";
// Parallel Merge Sort
vector<int> m2 = arr;
start = omp_get_wtime();
parallelMergeSort(m2, 0, n - 1);
end = omp_get_wtime();
cout << "Parallel Merge Sort time: " << (end - start) << " seconds\n";
return 0;
}
Output:
C:\Users\Admin\Desktop\Final year\Practical code\LP-V HPC>g++ -fopenmp -O2 parallel_sort.cpp -o parallel_sort
C:\Users\Admin\Desktop\Final year\Practical code\LP-V HPC>.\parallel_sort
Enter size of array: 50000
Sequential Bubble Sort time: 6.56 seconds
Parallel Bubble Sort time: 3.596 seconds
Sequential Merge Sort time: 0.0170002 seconds
Parallel Merge Sort time: 0.013 seconds
commented
HPC 02 Bubble and merger Commented:
#include <iostream> // For input/output operations
#include <vector> // For using the vector container
#include <cstdlib> // For rand() and srand()
#include <ctime> // For time() used to seed rand()
#include <omp.h> // For OpenMP functions and directives
using namespace std; // To avoid using std:: prefix repeatedly
// ------------------------------
// Sequential Bubble Sort
// ------------------------------
void bubbleSort(vector<int>& arr) {
int n = arr.size(); // Get size of the array
for (int i = 0; i < n - 1; i++) // Outer loop for number of passes
for (int j = 0; j < n - i - 1; j++) // Inner loop for comparisons
if (arr[j] > arr[j + 1]) // Compare adjacent elements
swap(arr[j], arr[j + 1]); // Swap if they are in wrong order
}
// ------------------------------
// Parallel Bubble Sort using Odd-Even Transposition Sort
// ------------------------------
void parallelBubbleSort(vector<int>& arr) {
int n = arr.size(); // Get size of array
for (int i = 0; i < n; i++) { // Perform n passes
#pragma omp parallel for // Parallelize this loop
for (int j = (i % 2); j < n - 1; j += 2) { // Odd or even indexed pairs
if (arr[j] > arr[j + 1]) // Compare
swap(arr[j], arr[j + 1]); // Swap if needed
}
}
}
// ------------------------------
// Merge function for Merge Sort
// ------------------------------
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m; // Lengths of left and right subarrays
vector<int> L(n1), R(n2); // Temp arrays for left and right halves
for (int i = 0; i < n1; i++) // Copy data to temp arrays
L[i] = arr[l + i];
for (int i = 0; i < n2; i++)
R[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l; // Merge back into arr[]
while (i < n1 && j < n2) // Compare and merge
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) // Copy remaining elements of L[]
arr[k++] = L[i++];
while (j < n2) // Copy remaining elements of R[]
arr[k++] = R[j++];
}
// ------------------------------
// Sequential Merge Sort
// ------------------------------
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // Calculate middle index
mergeSort(arr, l, m); // Sort left half
mergeSort(arr, m + 1, r); // Sort right half
merge(arr, l, m, r); // Merge the two halves
}
}
// ------------------------------
// Parallel Merge Sort using OpenMP Sections
// ------------------------------
void parallelMergeSort(vector<int>& arr, int l, int r, int depth = 0) {
if (l < r) {
int m = l + (r - l) / 2; // Calculate middle index
if (depth < 4) { // Limit recursion depth to avoid oversubscription
#pragma omp parallel sections // Parallelize with sections
{
#pragma omp section
parallelMergeSort(arr, l, m, depth + 1); // Left half
#pragma omp section
parallelMergeSort(arr, m + 1, r, depth + 1); // Right half
}
} else {
mergeSort(arr, l, m); // Fallback to sequential merge sort
mergeSort(arr, m + 1, r);
}
merge(arr, l, m, r); // Merge sorted halves
}
}
// ------------------------------
// Main function to test all sorting algorithms
// ------------------------------
int main() {
int n;
cout << "Enter size of array: ";
cin >> n; // Input array size
vector<int> arr(n); // Declare array of size n
srand(time(0)); // Seed for random number generation
for (int i = 0; i < n; i++) // Fill array with random numbers
arr[i] = rand() % 10000;
// Sequential Bubble Sort
vector<int> b1 = arr; // Copy original array
double start = omp_get_wtime(); // Record start time
bubbleSort(b1); // Perform sequential bubble sort
double end = omp_get_wtime(); // Record end time
cout << "Sequential Bubble Sort time: " << (end - start) << " seconds\n";
// Parallel Bubble Sort
vector<int> b2 = arr; // Copy original array
start = omp_get_wtime(); // Start timer
parallelBubbleSort(b2); // Perform parallel bubble sort
end = omp_get_wtime(); // Stop timer
cout << "Parallel Bubble Sort time: " << (end - start) << " seconds\n";
// Sequential Merge Sort
vector<int> m1 = arr; // Copy original array
start = omp_get_wtime(); // Start timer
mergeSort(m1, 0, n - 1); // Perform sequential merge sort
end = omp_get_wtime(); // Stop timer
cout << "Sequential Merge Sort time: " << (end - start) << " seconds\n";
// Parallel Merge Sort
vector<int> m2 = arr; // Copy original array
start = omp_get_wtime(); // Start timer
parallelMergeSort(m2, 0, n - 1); // Perform parallel merge sort
end = omp_get_wtime(); // Stop timer
cout << "Parallel Merge Sort time: " << (end - start) << " seconds\n";
return 0; // Exit program
}