UFMG - Pós-graduação em Ciência da Computação - Programação Paralela

A seguir: Transações Acima: Exercício 2 Anterior: Exercício 2

Comparação e Troca: Algoritmo

 

void sort(int a[],int n) {
		 for(int i = 0; i <n/2; i++) {
		 		 cobegin
		 		 		 $\parallel_{k=0}^{n/2}$ compareAndSwap(a[2k], a[2k+1]);
		 		 coend;
		 		 cobegin
		 		 		 $\parallel_{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.