Pages

Questão EPO - Quicksort

O Quick Sort é um dos método mais rápidos de ordenação, apesar de às vezes partições desequilibradas poderem conduzir a uma ordenação lenta. Esse método de ordenação utiliza a técnica divide and conquer (dividir o problema inicial em dois subproblemas e resolver um problema menor utilizando a recursividade). Porque é que a seguinte lista é pouco eficiente no método de ordenação do quick sort?  Lista: (9, 8, 7, 6, 5, 4, 3, 2, 1).

a) Visto que o algoritmo escolhe o primeiro elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada (decrescentemente).
b) Visto que o algoritmo escolhe o elemento central para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada
c)  Visto que o algoritmo escolhe o terceiro elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada
d) Visto que o algoritmo escolhe o último elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada (decrescentemente).
e) n.d.a

Fontes:
http://en.wikipedia.org/wiki/Quicksort
http://w3.ualg.pt/~hshah/ped/Aula%2014/Quick_final.html

Um comentário:

Anônimo disse...

Resposta: a

Postar um comentário

 
Copyright (c) 2010. Blogger templates by Bloggermint