Saturday 9 January 2016

Concurrent Quicksort Program in C++ using OPENMP

              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.

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:

Program: (concurrentquicksort.cpp)


#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";
}

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






3 comments:

  1. Hi Parag,
    I have tried this programming, it exceuted without any bugs. Informative post.
    Regards,
    web designing training|web designing training in chennai

    ReplyDelete
  2. 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.

    ReplyDelete
  3. Informative blog and it was up to the point describing the information very effectively. Thanks to blog author for wonderful and informative post...
    oracle training in chennai


    ReplyDelete