- - - - CENAPAD-MGCO

A seguir: Transações Acima: Respostas Anterior: Quicksort Paralelo

Comparação e Troca em Paralelo

 (Exercício 2.5.2)

 
void sort(int a[],int n) {     
   for(int i = 0; i < n/2; i++) {     
      cobegin   
         ||(k=0..n/2) compareAndSwap(a[2k], a[2k+1]);   
      coend;   
      cobegin   
         ||(k=1..n/2) compareAndSwap(a[2k-1],a[2k]);   
      coend;   
   }    
}

Claramente temos um algoritmo de complexidade $\mathbf{O}(n)$, para o pior caso, com desempenho bem superior ao do Quicksort paralelo. Este é um exemplo de que paralelizações de bons algoritmos sequenciais podem resultar em algoritmos paralelos ruins, e vice-versa.