Seminário de Teoria da Computação Heapsort /versus/ Quicksort Jorge Stolfi Sexta-feira, 10 de setembro de 2004, Auditório do IC 13:00hs Resumo: É sabido que heapsort, apesar de sua elegância, faz em média o dobro do número de comparações que quicksort faz (aproximadamente 2 N lg N contra N lg N). Pelo menos é o que dizem quase todos os livros-texto de algoritmos. Por esse motivo, quicksort tem a fama de ser o algoritmo de ordenação mais eficiente para dados aleatórios. Acontece que essa ineficiência do heapsort é devida a uma simplificação "inocente" que é tradicionalmente introduzida no algoritmo para economizar duas linhas de código. Tirando essa simplificação, o número de comparações do heapsort cai pela metade. Sob esse critério, ele fica um pouco mais eficiente que quicksort, pelo menos para N > 1000. Não está claro se este resultado continua valendo quando o critério é o tempo total de execução, em vez do número de comparações. Na verdade, sobe ambos os critérios, tanto heapsort quanto quicksort provavelmente perdem para outros algoritmos, como mergesort com merge /in loco/. Pelo visto, a análise de algoritmos de ordenação ainda está longe de ser um assunto fechado.