Pages

Questão EPO - Quicksort

Questão sobre Quick Sort:

“A grande vantagem desse algoritmo é que ele pode ser muito eficiente. O melhor caso ocorre quando o elemento pivô representa o valor mediano do conjunto dos elementos do vetor. Se isto acontece, após o posicionamento do pivô em sua posição, restará dois sub-vetores para serem ordenados, ambos com o número de elementos reduzido a metade, em relação ao vetor original. Pode-se mostrar que, neste melhor caso, o esforço computacional do algoritmo é proporcional a n log(n), e dizemos que o algoritmo é O(n log(n)). Um desempenho muito superior ao O(n2) apresentado pelo algoritmo de ordenação bolha. Infelizmente, não temos como garantir que o pivô seja o mediano.”
W. Celes

Qual algoritmo é comparado com o algoritmo de ordenação bolha no texto acima?

a) Bubble Sort;
b) Merge Sort;
c) Quick Sort;
d) Linked List;
e) N.D.A

Fonte:
Questão extraída e adaptada das Notas de aula dos Profs. Waldemar Celes e José Lucas Rangel PUC-RIO - Curso de Engenharia – 2002, disponível na Internet e da apresentação vista em aula.

Um comentário:

Luis Carlos disse...

O método que utiliza um pivô para separar o vetor e depois ordená-lo é o Quick Sort, portanto, resposta certa letra C

Postar um comentário

 
Copyright (c) 2010. Blogger templates by Bloggermint