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

A seguir: Exercício 2 Acima: Aula 7 - Exercícios Anterior: Aula 7 - Exercícios

Quicksort Paralelo - Algoritmo

Quicksort Paralelo - Algoritmo

 

void quicksort(int a[], int left, int right){
		 if(left < right) {
		 		 int pivot = choosePivot(a,left,right);
		 		 Partition p = partition(a, left, right, pivot);
		 		 cobegin
		 		 		 quicksort(a,left,p.right);
		 		 		 $\parallel$		 		 		 quicksort(a,p.left,right);
		 		 coend;
		 } 
} 

• Análise : Supondo que o pivot escolhido é sempre a mediana, o algoritmo fará n comparações na primeira partição. No segundo nível de recursividade serão feitas duas partições, cada uma de tamanho n/2; no total serão também feitas n comparações. Entretanto, como as partições são feitas simultaneamente, o tempo gasto será proporcional a n/2. No terceiro nível, teremos quatro partições simultâneas, cada uma de tamanho n/4, e assim por diante. Desta forma, o tempo total gasto será dado pela soma

  $$T = \frac{n}{1} + \frac{n}{2} + \cdots + 1 = n\left( 2 - 1/n\right)$$

  Temos portanto um sort com complexidade (para o melhor caso) de $\mathbf{O}(n)$, melhor do que o limite de $\mathbf{O}(n \log(n)$ para algoritmos sequenciais.
• O método partition pode ser implementado com paralelismo, o que reduz à metade o tempo ideal de processamento, mas não altera a ordem de complexidade.