Enunciado:
Dado o seguinte algoritmo para ordenar um vetor numérico em ordem descrescente, que combina características do Quicksort com função BUILD-MAX-HEAP apresentadas no livro Algoritmos (2a edição) de Thomas H. Cormen:

CEBOLINHASOLT(A, p, r)
  if p < r then
    BUILD-MAX-HEAP(A)
    q <- piso((p+r)/2)
    CEBOLINHASOLT(A, p, q)
    CEBOLINHASOLT(A, q+1, r)

A) O algoritmo funciona e é superior ao Quicksort pois seu tempo de execução no pior caso é O(n lg n).

B) O algoritmo funciona, mas possui tempo de execução cuja ordem de crescimento é equivalente ao Quicksort, pois o BUILD-MAX-HEAP possui tempo de execução O(n), equivalente ao tempo do PARTITION no Quicksort.

C) O algoritmo funciona mas é inferior ao Quicksort pois seu tempo se execução no melhor caso é O(n^2).

D) O algoritmo não funciona para todos os casos, pois o BUILD-MAX-HEAP não organiza o vetor de modo que se possa garantir que: todos os elementos cuja posição seja menor ou igual a q tenham valor superior (ou igual) àqueles elementos cuja posição seja maior que q .

E) NDA

Autor(a): André Santanchè