#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <mpi.h>
// Sequential Quicksort
void quicksort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivot = arr[low];
int i = low + 1;
int j = high;
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
std::swap(arr[i], arr[j]);
i++;
j--;
}
}
std::swap(arr[low], arr[j]);
quicksort(arr, low, j - 1);
quicksort(arr, j + 1, high);
}
}
// Parallel Quicksort using MPI
void parallelQuicksort(std::vector<int>& arr, int low, int high) {
int size, rank;
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (size == 1) {
quicksort(arr, low, high);
return;
}
int n = high - low + 1;
int pivot, partitionSize, partitionStart;
if (rank == 0) {
// Choose a random pivot
srand(time(nullptr));
int pivotIndex = rand() % n;
pivot = arr[low + pivotIndex];
// Broadcast the pivot to all processes
MPI_Bcast(&pivot, 1, MPI_INT, 0, MPI_COMM_WORLD);
// Partition the array
partitionSize = n / size;
partitionStart = low + pivotIndex - partitionSize / 2;
} else {
// Receive the broadcasted pivot
MPI_Bcast(&pivot, 1, MPI_INT, 0, MPI_COMM_WORLD);
// Calculate the partition size and start index
partitionSize = n / size;
partitionStart = low + rank * partitionSize;
}
// Allocate memory for the local partition
std::vector<int> localArr(partitionSize);
// Scatter the array to all processes
MPI_Scatter(&arr[partitionStart], partitionSize, MPI_INT,
&localArr[0], partitionSize, MPI_INT, 0, MPI_COMM_WORLD);
// Perform local quicksort
quicksort(localArr, 0, partitionSize - 1);
// Gather the sorted local partitions
MPI_Gather(&localArr[0], partitionSize, MPI_INT,
&arr[partitionStart], partitionSize, MPI_INT, 0, MPI_COMM_WORLD);
// Perform final sorting at rank 0
if (rank == 0) {
// Recursively sort the remaining elements
quicksort(arr, low, partitionStart - 1);
quicksort(arr, partitionStart + n / size, high);
}
}
int main(int argc, char** argv) {
MPI_Init(&argc, &argv);
int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == 0) {
std::vector<int> arr = {5, 2, 8, 12, 1, 6, 3, 9};
int n = arr.size();
std::cout << "Original array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
std::vector<int> seqArr = arr; // Copy of the original array for sequential sorting
double seqStartTime = MPI_Wtime();
quicksort(seqArr, 0, n - 1);
double seqEndTime = MPI_Wtime();
std::cout << "Sequential Quicksort - Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << seqArr[i] << " ";
}
std::cout << std::endl;
std::cout << "Sequential Quicksort - Execution time: " << (seqEndTime - seqStartTime) << " seconds" << std::endl;
}
MPI_Barrier(MPI_COMM_WORLD); // Wait for all processes to reach this point
std::vector<int> parArr = {5, 2, 8, 12, 1, 6, 3, 9}; // Copy of the original array for parallel sorting
double parStartTime = MPI_Wtime();
parallelQuicksort(parArr, 0, parArr.size() - 1);
double parEndTime = MPI_Wtime();
if (rank == 0) {
std::cout << "Parallel Quicksort - Sorted array: ";
for (int i = 0; i < parArr.size(); i++) {
std::cout << parArr[i] << " ";
}
std::cout << std::endl;
std::cout << "Parallel Quicksort - Execution time: " << (parEndTime - parStartTime) << " seconds" << std::endl;
}
MPI_Finalize();
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}