Mostre que a ordem de torneio exige
comparações para ordenar uma lista de
elementos. [Dica: Pela inserção de um número adequado de elementos fictícios definido
como menor do que todos os inteiros, tal como
, suponha que
para algum inteiro positivo
.]
como menor do que todos os inteiros, tal como
Passo 1
O enunciado pede para mostrar que o método de ordenação por torneio (selection tree) usa
comparações em uma lista de
elementos. A ideia é preencher até o próximo valor de potência de 2, usando elementos fictícios com valor
, para ter uma árvore completa de altura
com
. Vamos então contabilizar as comparações necessárias na construção da árvore e em cada extração do mínimo.
Passo 2
Construção inicial da árvore de torneio:
— Colocamos os elementos em folhas de uma árvore completa de tamanho
.
— Em cada nó interno, comparamos os valores de seus dois filhos e guardamos o vencedor (o menor).
Como há exatamente nós internos, a construção faz
comparações.
— Colocamos os
— Em cada nó interno, comparamos os valores de seus dois filhos e guardamos o vencedor (o menor).
Como há exatamente
comparações.
Passo 3
Extração de um elemento (o mínimo):
— O mínimo está na raiz. Para “remover” esse valor e continuar a ordenação, substituímos a folha correspondente por .
— Subimos pela árvore recomparando em cada nível: em cada nó interno acima da folha substituída, comparamos os dois filhos para decidir o novo vencedor.
Como a altura da árvore é , cada extração gasta
— O mínimo está na raiz. Para “remover” esse valor e continuar a ordenação, substituímos a folha correspondente por
— Subimos pela árvore recomparando em cada nível: em cada nó interno acima da folha substituída, comparamos os dois filhos para decidir o novo vencedor.
Como a altura da árvore é
comparações.
Passo 4
Complexidade total:
— Construção inicial: comparações.
— Extração de todos os elementos:
comparações.
Somando, o custo total é
— Construção inicial:
— Extração de todos os
Somando, o custo total é