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 \lceil\log_{2}N\rceil, com N folhas representando os elementos do vetor.
– Preencher folhas extras com o sentinela +\infty (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 +\infty e “rejogar” apenas no caminho folha→raiz.

Passo 2

Construção da árvore de torneio:
– Seja A[1\ldots N] o vetor de entrada.
– Calcule M = 2^{\lceil\log_{2}N\rceil}.
– Crie um array T[1\ldots 2M-1] de nós, onde cada nó armazena um par (\mathit{valor},\,\mathit{índice\_folha})í.
– Para i de 1 até N:
T[M+i-1] \leftarrow (A[i],\,M+i-1).
– Para i de N+1 até M:
T[M+i-1] \leftarrow (+\infty,\,M+i-1).

Passo 3

Jogar o torneio bottom-up para preencher os nós internos:
Para i de M-1 até 1 decrescendo:
Se T[2i].\mathit{valor} \le T[2i+1].\mathit{valor} então
T[i] \leftarrow T[2i]
senão
T[i] \leftarrow T[2i+1].

Passo 4

Extração iterativa dos vencedores para formar o vetor ordenado S[1\ldots N]:
Para k de 1 até N:
\,S[k] \leftarrow T[1].\mathit{valor} // raiz é o mínimo atual
– Seja j \leftarrow T[1].\mathit{índice\_folha}í.
– Atualize a folha: T[j].\mathit{valor} \leftarrow +\infty.
– Suba pelo caminho até a raiz:
Enquanto j>1:
j \leftarrow \lfloor j/2\rfloor
Se T[2j].\mathit{valor} \le T[2j+1].\mathit{valor} então
T[j] \leftarrow T[2j]
senão
T[j] \leftarrow T[2j+1].

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

Exercícios de Livros Relacionados