parallel Bubble sort using openmp

Question

i write a c++ code for Bubble sort algorithm and i dont know how to make it parallel using openmp so please help me ..... this is the code :

#include "stdafx.h"    
#include <iostream>
#include <time.h>
#include <omp.h>
using namespace std;

int a[40001];
void sortArray(int [], int);
int q=0;

int _tmain(int argc, _TCHAR* argv[])
{   
int x=40000;
int values[40000];
for (int i=0;i<x;i++)
{
    values[i]=rand();
}
cout << "Sorting Array .......\n";
clock_t start = clock();
sortArray(values, x);
 cout << "The Array Now Sorted\n";
printf("Elapsed Time : %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
cout << "\n";
}
 void sortArray(int array[], int size)  
{
  bool swap;
   int temp;
  do
  {
   swap = false;
  for (int count = 0; count < (size - 1); count++)
   {
   if (array[count] > array[count + 1])
  {
    temp = array[count];
    array[count] = array[count + 1];
    array[count + 1] = temp;
    swap = true;
  }
  }
  }while (swap);
}

it takes now about 13 seconds i tried to put ##pragma omp parallel for before "for statment" in sortArray method and it didnt make any difference it take also about 13 second ..... so please help me as fast as you can

You won't be able to parallelise the loop, since each iteration depends on the result of the previous iteration. If you want to speed it up, then use just about any algorithm except Bubblesort. Or, better still, use std::sort. — Mike Seymour
– Mike Seymour, Commented Jan 8, 2010 at 14:03
I think you missed something: you cannot ask several processors to each run on their own iteration, but you can parallelize an iteration. Basically if you have 6 elements [0,1,2,3,4,5], then you can have one processor work on [0,1], one on [2,3] and one on [4,5]. On the next iteration, you have one on [2,3] and one on [4,5] and then you are back to square one. — Matthieu M.
– Matthieu M., Commented Jan 8, 2010 at 17:26

Nick Dandoulakis · Accepted Answer · 2010-01-08 14:36:48Z

6

Try this Parallel Bubble Sort algorithm:

1.  For k = 0 to n-2
2.  If k is even then
3.     for i = 0 to (n/2)-1 do in parallel
4.         If A[2i] > A[2i+1] then
5.             Exchange A[2i] ↔ A[2i+1]
6.  Else
7.     for i = 0 to (n/2)-2 do in parallel
8.         If A[2i+1] > A[2i+2] then
9.             Exchange A[2i+1] ↔ A[2i+2]
10. Next k

Parallel Analysis

Steps 1-10 is a one big loop that is represented n -1 times. Therefore, the parallel time complexity is O(n). If the algorithm, odd-numbered steps need (n/2) - 2 processors and even-numbered steps require
(n/2) - 1 processors.Therefore, this needs O(n) processors.

You can still use a swap flag check to stop the routine right before Next k.
Of course don't expect great speed improvement without hundreds of physical processors :)

answered Jan 8, 2010 at 14:36

Nick Dandoulakis

43.3k17 gold badges106 silver badges139 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

parallel Bubble sort using openmp

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related