Descreva a ordem de torneio usando pseudocódigo.
Passo 1
O enunciado pede para descrever, via pseudocódigo, o Tournament Sort (ordem de torneio), que é um método de ordenação baseado em uma árvore binária completa onde cada nó interno armazena o “vencedor” (menor ou maior) entre seus dois filhos. Para isso, vamos precisar:
– Construir uma árvore completa de altura , com
folhas representando os elementos do vetor.
– Preencher folhas extras com o sentinela (caso a quantidade de folhas não seja potência de 2).
– Fazer um torneio bottom-up para determinar o valor mínimo em toda a árvore.
– Repetir: extrair o vencedor (raiz), substituir sua folha por e “rejogar” apenas no caminho folha→raiz.
– Construir uma árvore completa de altura
– Preencher folhas extras com o sentinela
– Fazer um torneio bottom-up para determinar o valor mínimo em toda a árvore.
– Repetir: extrair o vencedor (raiz), substituir sua folha por
Passo 2
Construção da árvore de torneio:
– Seja o vetor de entrada.
– Calcule .
– Crie um array de nós, onde cada nó armazena um par
.
– Para de
até
:
.
– Para de
até
:
.
– Seja
– Calcule
– Crie um array
– Para
– Para
Passo 3
Jogar o torneio bottom-up para preencher os nós internos:
Para de
até
decrescendo:
Se então
senão
.
Para
Se
senão
Passo 4
Extração iterativa dos vencedores para formar o vetor ordenado
:
Para de
até
:
– // raiz é o mínimo atual
– Seja .
– Atualize a folha: .
– Suba pelo caminho até a raiz:
Enquanto :
Se então
senão
.
Para
–
– Seja
– Atualize a folha:
– Suba pelo caminho até a raiz:
Enquanto
Se
senão
Resposta
procedure TournamentSort(A[1..N])
M ← \(2^{⌈lo\(g_{2}\)\) N⌉}
allocate T[1..2M−1] of (valor,índice_folha)
for i ← 1 to N do
T[\(M+i\)−1] ← (A[i], \(M+i\)−1)
for i ← N\(+1\) to M do
T[\(M+i\)−1] ← (\(+\infty\), \(M+i\)−1)
for i ← M−1 downto 1 do
if T[2i].valor ≤ T[2i\(+1\)].valor then
T[i] ← T[2i]
else
T[i] ← T[2i\(+1\)]
allocate S[1..N]
for k ← 1 to N do
S[k] ← T[1].valor
j ← T[1].índice_folha
T[j].valor ← \(+\infty\)
while j > 1 do
j ← ⌊j/2⌋
if T[2j].valor ≤ T[2j\(+1\)].valor then
T[j] ← T[2j]
else
T[j] ← T[2j\(+1\)]
return S