Implementation of Quick sort using MPI, OMP and Posix thread
QuickSort is a Divide and Conquer Algorithm. It picks an element as a pivot and partitions the array around the picked pivot. There are many ways of choosing the pivot elements. They are:
- Always pick the first element as a pivot.
- Always pick the last element as the pivot (implemented below)
- Pick a random element as a pivot.
- Pick median as a pivot.
MPI: MPI stands for Message Passing Interface. Here the message is data. MPI allows data to be passed between processes in a distributed memory environment. In C, “mpi.h” is a header file that includes all data structures, routines, and constants of MPI. Using “mpi.h” parallelized the quick sort algorithm. Below is the C program to implement quicksort using MPI:
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
// Function to swap two numbers
void swap(int* arr, int i, int j)
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Function that performs the Quick Sort
// for an array arr[] starting from the
// index start and ending at index end
void quicksort(int* arr, int start, int end)
{
int pivot, index;
// Base Case
if (end <= 1)
return;
// Pick pivot and swap with first
// element Pivot is middle element
pivot = arr[start + end / 2];
swap(arr, start, start + end / 2);
// Partitioning Steps
index = start;
// Iterate over the range [start, end]
for (int i = start + 1; i < start + end; i++) {
// Swap if the element is less
// than the pivot element
if (arr[i] < pivot) {
index++;
swap(arr, i, index);
}
}
// Swap the pivot into place
swap(arr, start, index);
// Recursive Call for sorting
// of quick sort function
quicksort(arr, start, index - start);
quicksort(arr, index + 1, start + end - index - 1);
}
// Function that merges the two arrays
int* merge(int* arr1, int n1, int* arr2, int n2)
{
int* result = (int*)malloc((n1 + n2) * sizeof(int));
int i = 0;
int j = 0;
int k;
for (k = 0; k < n1 + n2; k++) {
if (i >= n1) {
result[k] = arr2[j];
j++;
}
else if (j >= n2) {
result[k] = arr1[i];
i++;
}
// Indices in bounds as i < n1
// && j < n2
else if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
i++;
}
// v2[j] <= v1[i]
else {
result[k] = arr2[j];
j++;
}
}
return result;
}
// Driver Code
int main(int argc, char* argv[])
{
int number_of_elements;
int* data = NULL;
int chunk_size, own_chunk_size;
int* chunk;
FILE* file = NULL;
double time_taken;
MPI_Status status;
if (argc != 3) {
printf("Desired number of arguments are not their "
"in argv....\n");
printf("2 files required first one input and "
"second one output....\n");
exit(-1);
}
int number_of_process, rank_of_process;
int rc = MPI_Init(&argc, &argv);
if (rc != MPI_SUCCESS) {
printf("Error in creating MPI "
"program.\n "
"Terminating......\n");
MPI_Abort(MPI_COMM_WORLD, rc);
}
MPI_Comm_size(MPI_COMM_WORLD, &number_of_process);
MPI_Comm_rank(MPI_COMM_WORLD, &rank_of_process);
if (rank_of_process == 0) {
// Opening the file
file = fopen(argv[1], "r");
// Printing Error message if any
if (file == NULL) {
printf("Error in opening file\n");
exit(-1);
}
// Reading number of Elements in file ...
// First Value in file is number of Elements
printf(
"Reading number of Elements From file ....\n");
fscanf(file, "%d", &number_of_elements);
printf("Number of Elements in the file is %d \n",
number_of_elements);
// Computing chunk size
chunk_size
= (number_of_elements % number_of_process == 0)
? (number_of_elements / number_of_process)
: (number_of_elements / number_of_process
- 1);
data = (int*)malloc(number_of_process * chunk_size
* sizeof(int));
// Reading the rest elements in which
// operation is being performed
printf("Reading the array from the file.......\n");
for (int i = 0; i < number_of_elements; i++) {
fscanf(file, "%d", &data[i]);
}
// Padding data with zero
for (int i = number_of_elements;
i < number_of_process * chunk_size; i++) {
data[i] = 0;
}
// Printing the array read from file
printf("Elements in the array is : \n");
for (int i = 0; i < number_of_elements; i++) {
printf("%d ", data[i]);
}
printf("\n");
fclose(file);
file = NULL;
}
// Blocks all process until reach this point
MPI_Barrier(MPI_COMM_WORLD);
// Starts Timer
time_taken -= MPI_Wtime();
// BroadCast the Size to all the
// process from root process
MPI_Bcast(&number_of_elements, 1, MPI_INT, 0,
MPI_COMM_WORLD);
// Computing chunk size
chunk_size
= (number_of_elements % number_of_process == 0)
? (number_of_elements / number_of_process)
: number_of_elements
/ (number_of_process - 1);
// Calculating total size of chunk
// according to bits
chunk = (int*)malloc(chunk_size * sizeof(int));
// Scatter the chuck size data to all process
MPI_Scatter(data, chunk_size, MPI_INT, chunk,
chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
free(data);
data = NULL;
// Compute size of own chunk and
// then sort them
// using quick sort
own_chunk_size = (number_of_elements
>= chunk_size * (rank_of_process + 1))
? chunk_size
: (number_of_elements
- chunk_size * rank_of_process);
// Sorting array with quick sort for every
// chunk as called by process
quicksort(chunk, 0, own_chunk_size);
for (int step = 1; step < number_of_process;
step = 2 * step) {
if (rank_of_process % (2 * step) != 0) {
MPI_Send(chunk, own_chunk_size, MPI_INT,
rank_of_process - step, 0,
MPI_COMM_WORLD);
break;
}
if (rank_of_process + step < number_of_process) {
int received_chunk_size
= (number_of_elements
>= chunk_size
* (rank_of_process + 2 * step))
? (chunk_size * step)
: (number_of_elements
- chunk_size
* (rank_of_process + step));
int* chunk_received;
chunk_received = (int*)malloc(
received_chunk_size * sizeof(int));
MPI_Recv(chunk_received, received_chunk_size,
MPI_INT, rank_of_process + step, 0,
MPI_COMM_WORLD, &status);
data = merge(chunk, own_chunk_size,
chunk_received,
received_chunk_size);
free(chunk);
free(chunk_received);
chunk = data;
own_chunk_size
= own_chunk_size + received_chunk_size;
}
}
// Stop the timer
time_taken += MPI_Wtime();
// Opening the other file as taken form input
// and writing it to the file and giving it
// as the output
if (rank_of_process == 0) {
// Opening the file
file = fopen(argv[2], "w");
if (file == NULL) {
printf("Error in opening file... \n");
exit(-1);
}
// Printing total number of elements
// in the file
fprintf(
file,
"Total number of Elements in the array : %d\n",
own_chunk_size);
// Printing the value of array in the file
for (int i = 0; i < own_chunk_size; i++) {
fprintf(file, "%d ", chunk[i]);
}
// Closing the file
fclose(file);
printf("\n\n\n\nResult printed in output.txt file "
"and shown below: \n");
// For Printing in the terminal
printf("Total number of Elements given as input : "
"%d\n",
number_of_elements);
printf("Sorted array is: \n");
for (int i = 0; i < number_of_elements; i++) {
printf("%d ", chunk[i]);
}
printf(
"\n\nQuicksort %d ints on %d procs: %f secs\n",
number_of_elements, number_of_process,
time_taken);
}
MPI_Finalize();
return 0;
}
// C program to implement the Quick Sort
// Algorithm using MPI
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
using namespace std;
// Function to swap two numbers
void swap(int* arr, int i, int j)
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Function that performs the Quick Sort
// for an array arr[] starting from the
// index start and ending at index end
void quicksort(int* arr, int start, int end)
{
int pivot, index;
// Base Case
if (end <= 1)
return;
// Pick pivot and swap with first
// element Pivot is middle element
pivot = arr[start + end / 2];
swap(arr, start, start + end / 2);
// Partitioning Steps
index = start;
// Iterate over the range [start, end]
for (int i = start + 1; i < start + end; i++) {
// Swap if the element is less
// than the pivot element
if (arr[i] < pivot) {
index++;
swap(arr, i, index);
}
}
// Swap the pivot into place
swap(arr, start, index);
// Recursive Call for sorting
// of quick sort function
quicksort(arr, start, index - start);
quicksort(arr, index + 1, start + end - index - 1);
}
// Function that merges the two arrays
int* merge(int* arr1, int n1, int* arr2, int n2)
{
int* result = (int*)malloc((n1 + n2) * sizeof(int));
int i = 0;
int j = 0;
int k;
for (k = 0; k < n1 + n2; k++) {
if (i >= n1) {
result[k] = arr2[j];
j++;
}
else if (j >= n2) {
result[k] = arr1[i];
i++;
}
// Indices in bounds as i < n1
// && j < n2
else if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
i++;
}
// v2[j] <= v1[i]
else {
result[k] = arr2[j];
j++;
}
}
return result;
}
// Driver Code
int main(int argc, char* argv[])
{
int number_of_elements;
int* data = NULL;
int chunk_size, own_chunk_size;
int* chunk;
FILE* file = NULL;
double time_taken;
MPI_Status status;
if (argc != 3) {
printf("Desired number of arguments are not their "
"in argv....\n");
printf("2 files required first one input and "
"second one output....\n");
exit(-1);
}
int number_of_process, rank_of_process;
int rc = MPI_Init(&argc, &argv);
if (rc != MPI_SUCCESS) {
printf("Error in creating MPI "
"program.\n "
"Terminating......\n");
MPI_Abort(MPI_COMM_WORLD, rc);
}
MPI_Comm_size(MPI_COMM_WORLD, &number_of_process);
MPI_Comm_rank(MPI_COMM_WORLD, &rank_of_process);
if (rank_of_process == 0) {
// Opening the file
file = fopen(argv[1], "r");
// Printing Error message if any
if (file == NULL) {
printf("Error in opening file\n");
exit(-1);
}
// Reading number of Elements in file ...
// First Value in file is number of Elements
printf(
"Reading number of Elements From file ....\n");
fscanf(file, "%d", &number_of_elements);
printf("Number of Elements in the file is %d \n",
number_of_elements);
// Computing chunk size
chunk_size
= (number_of_elements % number_of_process == 0)
? (number_of_elements / number_of_process)
: (number_of_elements / number_of_process
- 1);
data = (int*)malloc(number_of_process * chunk_size
* sizeof(int));
// Reading the rest elements in which
// operation is being performed
printf("Reading the array from the file.......\n");
for (int i = 0; i < number_of_elements; i++) {
fscanf(file, "%d", &data[i]);
}
// Padding data with zero
for (int i = number_of_elements;
i < number_of_process * chunk_size; i++) {
data[i] = 0;
}
// Printing the array read from file
printf("Elements in the array is : \n");
for (int i = 0; i < number_of_elements; i++) {
printf("%d ", data[i]);
}
printf("\n");
fclose(file);
file = NULL;
}
// Blocks all process until reach this point
MPI_Barrier(MPI_COMM_WORLD);
// Starts Timer
time_taken -= MPI_Wtime();
// BroadCast the Size to all the
// process from root process
MPI_Bcast(&number_of_elements, 1, MPI_INT, 0,
MPI_COMM_WORLD);
// Computing chunk size
chunk_size
= (number_of_elements % number_of_process == 0)
? (number_of_elements / number_of_process)
: number_of_elements
/ (number_of_process - 1);
// Calculating total size of chunk
// according to bits
chunk = (int*)malloc(chunk_size * sizeof(int));
// Scatter the chuck size data to all process
MPI_Scatter(data, chunk_size, MPI_INT, chunk,
chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
free(data);
data = NULL;
// Compute size of own chunk and
// then sort them
// using quick sort
own_chunk_size = (number_of_elements
>= chunk_size * (rank_of_process + 1))
? chunk_size
: (number_of_elements
- chunk_size * rank_of_process);
// Sorting array with quick sort for every
// chunk as called by process
quicksort(chunk, 0, own_chunk_size);
for (int step = 1; step < number_of_process;
step = 2 * step) {
if (rank_of_process % (2 * step) != 0) {
MPI_Send(chunk, own_chunk_size, MPI_INT,
rank_of_process - step, 0,
MPI_COMM_WORLD);
break;
}
if (rank_of_process + step < number_of_process) {
int received_chunk_size
= (number_of_elements
>= chunk_size
* (rank_of_process + 2 * step))
? (chunk_size * step)
: (number_of_elements
- chunk_size
* (rank_of_process + step));
int* chunk_received;
chunk_received = (int*)malloc(
received_chunk_size * sizeof(int));
MPI_Recv(chunk_received, received_chunk_size,
MPI_INT, rank_of_process + step, 0,
MPI_COMM_WORLD, &status);
data = merge(chunk, own_chunk_size,
chunk_received,
received_chunk_size);
free(chunk);
free(chunk_received);
chunk = data;
own_chunk_size
= own_chunk_size + received_chunk_size;
}
}
// Stop the timer
time_taken += MPI_Wtime();
// Opening the other file as taken form input
// and writing it to the file and giving it
// as the output
if (rank_of_process == 0) {
// Opening the file
file = fopen(argv[2], "w");
if (file == NULL) {
printf("Error in opening file... \n");
exit(-1);
}
// Printing total number of elements
// in the file
fprintf(
file,
"Total number of Elements in the array : %d\n",
own_chunk_size);
// Printing the value of array in the file
for (int i = 0; i < own_chunk_size; i++) {
fprintf(file, "%d ", chunk[i]);
}
// Closing the file
fclose(file);
printf("\n\n\n\nResult printed in output.txt file "
"and shown below: \n");
// For Printing in the terminal
printf("Total number of Elements given as input : "
"%d\n",
number_of_elements);
printf("Sorted array is: \n");
for (int i = 0; i < number_of_elements; i++) {
printf("%d ", chunk[i]);
}
printf(
"\n\nQuicksort %d ints on %d procs: %f secs\n",
number_of_elements, number_of_process,
time_taken);
}
MPI_Finalize();
return 0;
}
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
public class ParallelQuickSortMPI {
public static void main(String[] args) {
int[] data = {1, 5, 7, 8, 9, 10};
Arrays.parallelSort(data);
try (BufferedWriter writer = new BufferedWriter(new FileWriter("output.txt"))) {
writer.write("Sorted array is: ");
for (int num : data) {
writer.write(num + " ");
}
} catch (IOException e) {
e.printStackTrace();
System.exit(1);
}
System.out.println("Sorted array is: ");
for (int num : data) {
System.out.print(num + " ");
}
System.out.println();
}
}
# Function to perform Quick Sort
def quicksort(arr, start, end):
if end <= start + 1:
return
pivot = arr[start + (end - start) // 2]
arr[start], arr[start + (end - start) // 2] = arr[start + (end - start) // 2], arr[start]
index = start
for i in range(start + 1, start + end):
if arr[i] < pivot:
index += 1
arr[i], arr[index] = arr[index], arr[i]
arr[start], arr[index] = arr[index], arr[start]
quicksort(arr, start, index - start)
quicksort(arr, index + 1, start + end - index - 1)
# Function to merge two arrays
def merge(arr1, arr2):
result = []
i = 0
j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
return result + arr1[i:] + arr2[j:]
# Driver Code
data = [10, 7, 8, 9, 1, 5]
n = len(data)
quicksort(data, 0, n)
print("Sorted array:", data)
// Function to swap two numbers
function swap(arr, i, j) {
let t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Function that performs the Quick Sort
function quicksort(arr, start, end) {
if (end <= 1)
return;
let pivot = arr[start + Math.floor(end / 2)];
swap(arr, start, start + Math.floor(end / 2));
let index = start;
for (let i = start + 1; i < start + end; i++) {
if (arr[i] < pivot) {
index++;
swap(arr, i, index);
}
}
swap(arr, start, index);
quicksort(arr, start, index - start);
quicksort(arr, index + 1, start + end - index - 1);
}
// Function that merges the two arrays
function merge(arr1, arr2) {
let result = [];
let i = 0;
let j = 0;
while(i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
return result.concat(arr1.slice(i)).concat(arr2.slice(j));
}
// Driver Code
let data = [10, 7, 8, 9, 1, 5];
let n = data.length;
quicksort(data, 0, n);
console.log("Sorted array: " + data);
Output:
OMP: OMP is Open Multi-Processing. It’s an Application Program Interface (API) that may be used to explicitly direct multi-threaded, shared memory parallelism. In C/ C++, “omp.h” is a header file that includes all the related directives related to OMP. Using “omp.h” parallelized quick sort. Below are the programs to implement the above concept:
// C++ program to implement the Quick Sort
// using OMI
#include <bits/stdc++.h>
#include <omp.h>
using namespace std;
// Function to swap two numbers a and b
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// Function to perform the partitioning
// of array arr[]
int partition(int arr[], int start, int end)
{
// Declaration
int pivot = arr[end];
int i = (start - 1);
// Rearranging the array
for (int j = start; j <= end - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[end]);
// Returning the respective index
return (i + 1);
}
// Function to perform QuickSort Algorithm
// using openmp
void quicksort(int arr[], int start, int end)
{
// Declaration
int index;
if (start < end) {
// Getting the index of pivot
// by partitioning
index = partition(arr, start, end);
// Parallel sections
#pragma omp parallel sections
{
#pragma omp section
{
// Evaluating the left half
quicksort(arr, start, index - 1);
}
#pragma omp section
{
// Evaluating the right half
quicksort(arr, index + 1, end);
}
}
}
}
// Driver Code
int main()
{
// Declaration
int N;
// Taking input the number of
// elements we wants
cout << "Enter the number of elements"
<< " you want to Enter\n";
cin >> N;
// Declaration of array
int arr[N];
cout << "Enter the array: \n";
// Taking input that array
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
// Calling quicksort having parallel
// code implementation
quicksort(arr, 0, N - 1);
// Printing the sorted array
cout << "Array after Sorting is: \n";
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
return 0;
}
import java.util.Scanner;
public class QuickSort {
// Function to swap two numbers a and b
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to perform the partitioning of array arr[]
static int partition(int[] arr, int start, int end) {
// Declaration
int pivot = arr[end];
int i = start - 1;
// Rearranging the array
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
// Returning the respective index
return i + 1;
}
// Function to perform QuickSort Algorithm
static void quicksort(int[] arr, int start, int end) {
// Declaration
if (start < end) {
// Getting the index of pivot by partitioning
int index = partition(arr, start, end);
// Evaluating the left half
quicksort(arr, start, index - 1);
// Evaluating the right half
quicksort(arr, index + 1, end);
}
}
// Driver Code
public static void main(String[] args) {
// Declaration
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of elements you want to Enter");
int N = scanner.nextInt();
// Declaration of array
int[] arr = new int[N];
System.out.println("Enter the array: ");
// Taking input that array
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt();
}
// Calling quicksort
quicksort(arr, 0, N - 1);
// Printing the sorted array
System.out.println("Array after Sorting is: ");
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
}
}
import java.util.Scanner;
public class QuickSort {
// Function to swap two numbers a and b
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to perform the partitioning of array arr[]
static int partition(int[] arr, int start, int end) {
// Declaration
int pivot = arr[end];
int i = start - 1;
// Rearranging the array
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
// Returning the respective index
return i + 1;
}
// Function to perform QuickSort Algorithm
static void quicksort(int[] arr, int start, int end) {
// Declaration
if (start < end) {
// Getting the index of pivot by partitioning
int index = partition(arr, start, end);
// Evaluating the left half
quicksort(arr, start, index - 1);
// Evaluating the right half
quicksort(arr, index + 1, end);
}
}
// Driver Code
public static void main(String[] args) {
// Declaration
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of elements you want to Enter");
int N = scanner.nextInt();
// Declaration of array
int[] arr = new int[N];
System.out.println("Enter the array: ");
// Taking input that array
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt();
}
// Calling quicksort
quicksort(arr, 0, N - 1);
// Printing the sorted array
System.out.println("Array after Sorting is: ");
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
}
}
// JavaScript program to implement the Quick Sort
// Function to swap two numbers a and b
function swap(a, b) {
let t = a;
a = b;
b = t;
return [a, b];
}
// Function to perform the partitioning of array arr[]
function partition(arr, start, end) {
// Declaration
let pivot = arr[end];
let i = start - 1;
// Rearranging the array
for (let j = start; j <= end - 1; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = swap(arr[i], arr[j]);
}
}
[arr[i + 1], arr[end]] = swap(arr[i + 1], arr[end]);
// Returning the respective index
return i + 1;
}
// Function to perform QuickSort Algorithm
function quicksort(arr, start, end) {
// Declaration
let index;
if (start < end) {
// Getting the index of pivot by partitioning
index = partition(arr, start, end);
// Evaluating the left half
quicksort(arr, start, index - 1);
// Evaluating the right half
quicksort(arr, index + 1, end);
}
}
// Driver Code
function main() {
// Declaration
let N = prompt("Enter the number of elements you want to Enter");
// Declaration of array
let arr = [];
console.log("Enter the array: ");
// Taking input that array
for (let i = 0; i < N; i++) {
arr[i] = prompt("Enter element " + (i+1));
}
// Calling quicksort
quicksort(arr, 0, N - 1);
// Printing the sorted array
console.log("Array after Sorting is: ");
console.log(arr.join(" "));
}
main();
Output:
POSIX Threads: The POSIX thread libraries are a C/C++ thread API based on standards. It enables the creation of a new concurrent process flow. It works well on multi-processor or multi-core systems, where the process flow may be scheduled to execute on another processor, increasing speed through parallel or distributed processing. Below is the C++ program to implement quicksort using POSIX threads:
// C++ program to implement the Quick Sort
// using POSIX Thread
#include <bits/stdc++.h>
#include <pthread.h>
using namespace std;
// Structure
struct data_set {
int start_index;
int end_index;
int* data;
};
// Function to perform swap operations
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// Partition function for making
// partition in array
int partition(int arr[], int left_index,
int right_index)
{
// Declaration and initialization
// choosing pivot element form which
// we make partition
// Here pivot is last element of
// the array
int pivot = arr[right_index];
int i = left_index - 1;
// Making array as per requirement
// arranging element smaller than
// pivot on left side and larger
// then pivot on right side
for (int j = left_index;
j <= right_index - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[right_index]);
// Returning the partition index
return i + 1;
}
// Quicksort Function for sorting
// array
void* quick_sort(void* data)
{
// Retrieving back the data sent
// from thread
struct data_set* info = (struct data_set*)data;
// Declaration of left index
int left_index, right_index, index;
// Initialization of left and
// right index
left_index = info->start_index;
right_index = info->end_index;
// Recursive call of quick_sort
// function
if (left_index < right_index) {
// Declaration of pthread and
// pthread attribute type object
pthread_attr_t attr;
pthread_t first_thread;
pthread_t second_thread;
// Making two pointers of type
// data_set for making again
// call form thread
struct data_set* info1 = new data_set;
struct data_set* info2 = new data_set;
// Their initialization
info1->data = info->data;
info2->data = info->data;
// Initialize of pthread attribute
pthread_attr_init(&attr);
// For setting the set detach
// state of attribute
pthread_attr_setdetachstate(
&attr, PTHREAD_CREATE_JOINABLE);
// Partition the array for any
// recursive call
index = partition(info->data,
left_index,
right_index);
info1->start_index = left_index;
info1->end_index = index - 1;
// Create pthread type object and
// printing the error if any
if (pthread_create(&first_thread,
&attr, quick_sort,
info1)) {
cout << "Error in creating thread "
<< endl;
// Exiting in case of not
// creation of thread
exit(-1);
}
info2->start_index = index + 1;
info2->end_index = right_index;
// Creating pthread type object
// and print the error
if (pthread_create(&second_thread,
&attr, quick_sort,
info2)) {
cout << "Error in creating thread "
<< endl;
// Exiting in case of not
// creation of thread
exit(-1);
}
// Joining the threads
pthread_join(first_thread, NULL);
pthread_join(second_thread, NULL);
}
return NULL;
}
// Driver Code
int main()
{
// Declaration of Number of threads
int N;
struct data_set* info = new data_set;
// Taking number of elements as input
cout << "Enter number of elements"
<< " in the array: \n";
cin >> N;
// Declaration of array
int A[N];
// Initialization of array
cout << "Enter the array: " << endl;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
// Initialize of structure of
// data_set type
info->data = A;
info->start_index = 0;
info->end_index = N - 1;
// Declaration of pthread object
pthread_t thread_id;
// Creating and pthread object and
// printing the array of any
if (pthread_create(&thread_id, NULL,
quick_sort,
info)) {
cout << "Error in creating thread"
<< endl;
// Exit in case of error
exit(-1);
}
// Joining the pthread object
int r1 = pthread_join(thread_id, NULL);
// Printing the array if any in case
// of joining
if (r1) {
cout << "Error in joining thread"
<< endl;
// Exiting in case of error
exit(-1);
}
// Printing the array after sorting
cout << "Sorted Array is: " << endl;
for (int i = 0; i < N; i++) {
cout << A[i] << " ";
}
cout << endl;
// Exiting from pthread programming
pthread_exit(NULL);
return 0;
}
import java.util.Scanner;
// Structure
class DataSet {
int startIndex;
int endIndex;
int[] data;
// Constructor
DataSet(int startIndex, int endIndex, int[] data) {
this.startIndex = startIndex;
this.endIndex = endIndex;
this.data = data;
}
}
public class Main {
// Function to perform swap operations
static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// Partition function for making partition in array
static int partition(int[] arr, int leftIndex, int rightIndex) {
int pivot = arr[rightIndex];
int i = leftIndex - 1;
for (int j = leftIndex; j <= rightIndex - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, rightIndex);
return i + 1;
}
// Quicksort Function for sorting array
static void quickSort(DataSet info) {
int leftIndex = info.startIndex;
int rightIndex = info.endIndex;
if (leftIndex < rightIndex) {
int index = partition(info.data, leftIndex, rightIndex);
DataSet info1 = new DataSet(leftIndex, index - 1, info.data);
DataSet info2 = new DataSet(index + 1, rightIndex, info.data);
Thread firstThread = new Thread(() -> quickSort(info1));
Thread secondThread = new Thread(() -> quickSort(info2));
firstThread.start();
secondThread.start();
try {
firstThread.join();
secondThread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
// Taking number of elements as input
Scanner scanner = new Scanner(System.in);
System.out.println("Enter number of elements in the array:");
int n = scanner.nextInt();
// Declaration of array
int[] arr = new int[n];
// Initialization of array
System.out.println("Enter the array:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Initialize the structure of DataSet type
DataSet info = new DataSet(0, n - 1, arr);
// Create and start a thread
Thread thread = new Thread(() -> quickSort(info));
thread.start();
try {
thread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
// Printing the sorted array
System.out.println("Sorted Array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
import threading
# Function to perform swap operations
def swap(a, b):
a, b = b, a
return a, b
# Partition function for making partition in array
def partition(arr, left_index, right_index):
pivot = arr[right_index]
i = left_index - 1
for j in range(left_index, right_index):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = swap(arr[i], arr[j])
arr[i + 1], arr[right_index] = swap(arr[i + 1], arr[right_index])
# Returning the partition index
return i + 1
# Quicksort Function for sorting array
def quick_sort(arr, left_index, right_index):
if left_index < right_index:
index = partition(arr, left_index, right_index)
# Creating two threads
first_thread = threading.Thread(target=quick_sort, args=(arr, left_index, index - 1))
second_thread = threading.Thread(target=quick_sort, args=(arr, index + 1, right_index))
# Starting the threads
first_thread.start()
second_thread.start()
# Waiting for the threads to finish
first_thread.join()
second_thread.join()
# Driver Code
def main():
# Taking number of elements as input
N = int(input("Enter number of elements in the array: \n"))
# Initialization of array
print("Enter the array: ")
A = list(map(int, input().split()))
# Call quick_sort function
quick_sort(A, 0, N - 1)
# Printing the array after sorting
print("Sorted Array is: ")
print(' '.join(map(str, A)))
if __name__ == "__main__":
main()
// Define the DataSet class to represent the data_set structure
class DataSet {
constructor(startIndex, endIndex, data) {
this.startIndex = startIndex;
this.endIndex = endIndex;
this.data = data;
}
}
// Function to perform swap operations
function swap(arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// Partition function for making partition in array
function partition(arr, leftIndex, rightIndex) {
// Choosing pivot element from the right end of the array
let pivot = arr[rightIndex];
let i = leftIndex - 1;
// Making partition such that elements smaller than pivot
// are on the left side and elements greater are on the right side
for (let j = leftIndex; j <= rightIndex - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, rightIndex);
// Returning the partition index
return i + 1;
}
// Quicksort function for sorting array
function quickSort(info) {
if (info.startIndex < info.endIndex) {
// Partitioning the array
let index = partition(info.data, info.startIndex, info.endIndex);
// Recursively calling quicksort on the left and right subarrays
quickSort(new DataSet(info.startIndex, index - 1, info.data));
quickSort(new DataSet(index + 1, info.endIndex, info.data));
}
}
// Driver code
function main() {
// Taking number of elements as input
let N = parseInt(prompt("Enter number of elements in the array: "));
// Taking array elements as input
let A = [];
for (let i = 0; i < N; i++) {
A.push(parseInt(prompt("Enter element " + (i + 1) + ": ")));
}
// Creating a DataSet object
let info = new DataSet(0, N - 1, A);
// Sorting the array using quicksort
quickSort(info);
// Printing the sorted array
console.log("Sorted Array is: ");
console.log(info.data.join(" "));
}
// Calling the main function to execute the program
main();
Output: