In this post, we will see how to
implement Quick sort algorithm concurrently(parallelly) in C++ language. (For implementation in C language, check http://www.comrevo.com/2015/08/concurrent-quicksort-program-in-c-using-openmp.html)
To make it concurrent/parallel, we will use OPENMP API. OPENMP is available alongwith gcc/g++ compiler.
In Quick sort, input is any sequence of numbers and output is Sorted array(here we will consider ascending order). We start with one number, mostly the first number, and finds its position in sorted array. This number is called pivot element. Then we divide the array into two parts considering this pivot element's position in sorted array. In each part, separately, we find the pivot elements. This process continues until all numbers are processed and we get the sorted array.
In Concurrent Quick sort, each part is processed by independent thread i.e. different threads will find out pivot element in each part recursively. Check in following diagram. Here PE stands for Pivot Element.
Program: (concurrentquicksort.cpp)
How To Run:
To Compile:
>>>g++ -fopenmp concurrentquicksort.cpp
(Note: -fopenmp is used to add OPENMP libraries to the program)
To Run:
>>>./a.out
Output:
Next: OpenMP Program for Merge Sort
Previous: Concurrent Quicksort Program in C using OPENMP
In Quick sort, input is any sequence of numbers and output is Sorted array(here we will consider ascending order). We start with one number, mostly the first number, and finds its position in sorted array. This number is called pivot element. Then we divide the array into two parts considering this pivot element's position in sorted array. In each part, separately, we find the pivot elements. This process continues until all numbers are processed and we get the sorted array.
In Concurrent Quick sort, each part is processed by independent thread i.e. different threads will find out pivot element in each part recursively. Check in following diagram. Here PE stands for Pivot Element.
Array ----------------------------------------------------------------------------------
Thread 0
Array -----------------------------------------PE0-----------------------------------
Thread 1 Thread 2
Array -------------------PE1----------------PE0--------------PE2-----------------
Thread 3 Thread 4 Thread 5 Thread 6
.
.
.
.
.
.
Watch OpenMP Basics with Example in following video:
#include<iostream>
#include<omp.h>
using namespace std;
int k=0;
class array
{
public:
int partition(int arr[], int low_index, int high_index)
{
int i, j, temp, key;
key = arr[low_index];
i= low_index + 1;
j= high_index;
while(1)
{
while(i < high_index && key >= arr[i])
i++;
while(key < arr[j])
j--;
if(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
temp= arr[low_index];
arr[low_index] = arr[j];
arr[j]= temp;
return(j);
}
}
}
void quicksort(int arr[], int low_index, int high_index)
{
int j;
if(low_index < high_index)
{
j = partition(arr, low_index, high_index);
cout<<"Pivot element with index "<<j<<" has been found out by thread "<<k<<"\n";
#pragma omp parallel sections
{
#pragma omp section
{
k=k+1;
quicksort(arr, low_index, j - 1);
}
#pragma omp section
{
k=k+1;
quicksort(arr, j + 1, high_index);
}
}
}
}
};
int main()
{
array a;
int arr[100];
int n,i;
cout<<"Enter the value of n\n";
cin>>n;
cout<<"Enter the "<<n<<" number of elements \n";
for(i=0;i<n;i++)
{
cin>>arr[i];
}
a.quicksort(arr, 0, n - 1);
cout<<"Elements of array after sorting \n";
for(i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
cout<<"\n";
}
#include<omp.h>
using namespace std;
int k=0;
class array
{
public:
int partition(int arr[], int low_index, int high_index)
{
int i, j, temp, key;
key = arr[low_index];
i= low_index + 1;
j= high_index;
while(1)
{
while(i < high_index && key >= arr[i])
i++;
while(key < arr[j])
j--;
if(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
temp= arr[low_index];
arr[low_index] = arr[j];
arr[j]= temp;
return(j);
}
}
}
void quicksort(int arr[], int low_index, int high_index)
{
int j;
if(low_index < high_index)
{
j = partition(arr, low_index, high_index);
cout<<"Pivot element with index "<<j<<" has been found out by thread "<<k<<"\n";
#pragma omp parallel sections
{
#pragma omp section
{
k=k+1;
quicksort(arr, low_index, j - 1);
}
#pragma omp section
{
k=k+1;
quicksort(arr, j + 1, high_index);
}
}
}
}
};
int main()
{
array a;
int arr[100];
int n,i;
cout<<"Enter the value of n\n";
cin>>n;
cout<<"Enter the "<<n<<" number of elements \n";
for(i=0;i<n;i++)
{
cin>>arr[i];
}
a.quicksort(arr, 0, n - 1);
cout<<"Elements of array after sorting \n";
for(i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
cout<<"\n";
}
How To Run:
To Compile:
>>>g++ -fopenmp concurrentquicksort.cpp
(Note: -fopenmp is used to add OPENMP libraries to the program)
To Run:
>>>./a.out
Output:
Next: OpenMP Program for Merge Sort
Previous: Concurrent Quicksort Program in C using OPENMP
Hi Parag,
ReplyDeleteI have tried this programming, it exceuted without any bugs. Informative post.
Regards,
web designing training|web designing training in chennai
This program was really helpful for me.But i want more coding because i am beginner of web designing & also do Hadoop Training in Chennaiclasses.
ReplyDeleteInformative blog and it was up to the point describing the information very effectively. Thanks to blog author for wonderful and informative post...
ReplyDeleteoracle training in chennai