- - - - CENAPAD-MGCO

A seguir: Comparação e Troca em Acima: Respostas Anterior: Respostas

Quicksort Paralelo

 (Exercício 2.5.1)

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);   
         ||  
         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.