Bubble parallèle trier par OpenMP

Question

i écrire un code C++ pour l'algorithme de tri Bubble et je ne sais pas comment le rendre parallèle à l'aide OpenMP donc s'il vous plaît aidez-moi ..... Voici le 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); 
} 

il faut maintenant environ 13 secondes, j'ai essayé de mettre ## pragma omp parallèle pour avant "pour la déclaration" dans la méthode sortArray et il n'a pas fait de différence, il faut aussi environ 13 secondes ..... alors s'il vous plaît aidez-moi aussi vite comme vous pouvez

Answer 1

Essayez ce Parallel Bubble Sort algorithme:

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 

analyse parallèle

étapes 1-10 est une grande boucle qui est représentée n-1 fois. Par conséquent, la complexité en temps parallèle est O (n). Si l'algorithme, les étapes impaires nécessitent (n/2) - 2 processeurs et les étapes paires nécessitent
(n/2) - 1 processeurs.Par conséquent, cela nécessite O (n) processeurs.

Vous pouvez toujours utiliser un chèque pour arrêter la bonne routine swap drapeau avant Next k.
Bien sûr, ne vous attendez pas à une amélioration rapide de la vitesse sans des centaines de processeurs physiques :)