Bubblesort Iteração Analisada

Primeiro, vamos relembrar como funciona o Bubblesort (na sua forma mais “clássica”):

1. Partindo do início do array, comparamos pares de elementos adjacentes e trocamos quando estão fora de ordem (o maior vai “borbulhando” para o fim).
2. Concluída a varredura do array (primeira iteração principal), o maior elemento já estará na última posição.
3. Repetimos o processo nas iterações seguintes, cada vez precisando comparar até a penúltima posição efetivamente não-ordenada.
4. Após $n-1$ iterações principais (em um array de tamanho $n$), o array estará ordenado.

---

Passo a passo do Bubblesort no array $[4,\, 2,\, 5,\, 0,\, 1,\, 7,\, 3,\, 8]$

Vamos exibir o estado do array apenas ao final de cada iteração principal.

Iteração 1

• Array inicial: $[4,\, 2,\, 5,\, 0,\, 1,\, 7,\, 3,\, 8]$.

• Comparações e trocas dentro dessa 1ª varredura:

  1. Compare $4$ e $2$ $\to$ troca $\to [2,\, 4,\, 5,\, 0,\, 1,\, 7,\, 3,\, 8]$
  2. Compare $4$ e $5$ $\to$ sem troca
  3. Compare $5$ e $0$ $\to$ troca $\to [2,\, 4,\, 0,\, 5,\, 1,\, 7,\, 3,\, 8]$
  4. Compare $5$ e $1$ $\to$ troca $\to [2,\, 4,\, 0,\, 1,\, 5,\, 7,\, 3,\, 8]$
  5. Compare $5$ e $7$ $\to$ sem troca
  6. Compare $7$ e $3$ $\to$ troca $\to [2,\, 4,\, 0,\, 1,\, 5,\, 3,\, 7,\, 8]$
  7. Compare $7$ e $8$ $\to$ sem troca

• Array ao final da 1ª iteração:

  $$[2,\, 4,\, 0,\, 1,\, 5,\, 3,\, 7,\, 8]$$

Iteração 2

• Estado inicial desta varredura: $[2,\, 4,\, 0,\, 1,\, 5,\, 3,\, 7,\, 8]$.

• Comparações e trocas:

  1. Compare $2$ e $4$ $\to$ sem troca
  2. Compare $4$ e $0$ $\to$ troca $\to [2,\, 0,\, 4,\, 1,\, 5,\, 3,\, 7,\, 8]$
  3. Compare $4$ e $1$ $\to$ troca $\to [2,\, 0,\, 1,\, 4,\, 5,\, 3,\, 7,\, 8]$
  4. Compare $4$ e $5$ $\to$ sem troca
  5. Compare $5$ e $3$ $\to$ troca $\to [2,\, 0,\, 1,\, 4,\, 3,\, 5,\, 7,\, 8]$
  6. Compare $5$ e $7$ $\to$ sem troca
  7. Compare $7$ e $8$ $\to$ sem troca

• Array ao final da 2ª iteração:

  $$[2,\, 0,\, 1,\, 4,\, 3,\, 5,\, 7,\, 8]$$

Iteração 3

• Estado inicial desta varredura: $[2,\, 0,\, 1,\, 4,\, 3,\, 5,\, 7,\, 8]$.

• Comparações e trocas:

  1. Compare $2$ e $0$ $\to$ troca $\to [0,\, 2,\, 1,\, 4,\, 3,\, 5,\, 7,\, 8]$
  2. Compare $2$ e $1$ $\to$ troca $\to [0,\, 1,\, 2,\, 4,\, 3,\, 5,\, 7,\, 8]$
  3. Compare $2$ e $4$ $\to$ sem troca
  4. Compare $4$ e $3$ $\to$ troca $\to [0,\, 1,\, 2,\, 3,\, 4,\, 5,\, 7,\, 8]$
  5. Compare $4$ e $5$ $\to$ sem troca
  6. Compare $5$ e $7$ $\to$ sem troca
  7. Compare $7$ e $8$ $\to$ sem troca

• Array ao final da 3ª iteração:

  $$[0,\, 1,\, 2,\, 3,\, 4,\, 5,\, 7,\, 8]$$

Iteração 4

• Estado inicial: $[0,\, 1,\, 2,\, 3,\, 4,\, 5,\, 7,\, 8]$.

• Ao comparar todos os pares, não ocorre mais nenhuma troca, pois tudo já está ordenado.

• Array ao final da 4ª iteração:

  $$[0,\, 1,\, 2,\, 3,\, 4,\, 5,\, 7,\, 8]$$

---

Conclusão

As transformações ao final de cada iteração principal foram:

1. $\color{blue}{[2,\;4,\;0,\;1,\;5,\;3,\;7,\;8]}$
2. $\color{blue}{[2,\;0,\;1,\;4,\;3,\;5,\;7,\;8]}$
3. $\color{blue}{[0,\;1,\;2,\;3,\;4,\;5,\;7,\;8]}$
4. $\color{blue}{[0,\;1,\;2,\;3,\;4,\;5,\;7,\;8]}$

Comparando com as alternativas fornecidas, a única que exibe exatamente essa sequência de estados (ao final de cada iteração) é a alternativa (a).

Para um grafo não dirigido (sem laços ou múltiplas arestas) com $n$ vértices, o número máximo de arestas ocorre no grafo completo $K_n$. Nesse caso, cada vértice se liga a todos os outros, e a quantidade total de arestas é dada por:

$$\frac{n\,(n-1)}{2}.$$

Portanto, a resposta correta é:

(b) $\displaystyle \frac{n(n-1)}{2}$.

Vamos analisar sucintamente cada alternativa no contexto de tabelas de dispersão (hash) com:

1. Encadeamento separado (Separate Chaining):

   • Cada posição na tabela (bucket) aponta para uma estrutura auxiliar (tipicamente, uma lista ligada) que contém todos os elementos que colidiram naquela posição.

2. Endereçamento aberto (Open Addressing):

   • Toda inserção e busca são resolvidas dentro do próprio arranjo (tabela), usando sondagens (linear, quadrática ou dupla dispersão) para encontrar a posição livre ou elemento na tabela.

---

Analisando cada alternativa

a) Maior complexidade do código devido à utilização de dupla dispersão.

• Dupla dispersão (double hashing) é uma forma de endereçamento aberto, não está relacionada especificamente ao encadeamento separado. Logo, não é a desvantagem típica de tabelas com encadeamento separado.

b) Uso adicional de memória.

• No encadeamento separado, cada posição da tabela precisa armazenar ponteiro(s) para uma estrutura de encadeamento (geralmente listas), além do próprio arranjo principal. Isso exige memória extra (para nós/ponteiros) em comparação ao endereçamento aberto.
• Essa é, de fato, uma desvantagem do encadeamento separado.

c) Maior probabilidade de colisões devido à utilização de listas ligadas.

• A probabilidade de colisão depende principalmente da função de hash e do fator de carga (load factor), não do fato de usar lista ligada. A lista ligada é apenas o mecanismo para lidar com colisões, não a causa de elas aumentarem.

d) Desempenho ruim quando a tabela está muito cheia.

• Quando a tabela fica cheia, tanto encadeamento separado quanto endereçamento aberto podem ter desempenho degradado. Porém, no encadeamento separado, podemos até inserir mais elementos que o tamanho do arranjo (load factor > 1), embora as listas fiquem mais compridas. Já o endereçamento aberto sofre ainda mais quando a tabela está muito cheia (sondagens ficam mais longas). Então não é uma desvantagem exclusiva do encadeamento separado; pode acontecer em ambas as abordagens.

e) Incapacidade de reutilizar facilmente espaço de chaves apagadas na tabela.

• Essa é uma desvantagem típica do endereçamento aberto, pois ao remover um elemento temos que marcar a posição como “tombstone” para não quebrar a sequência de sondagem. No encadeamento separado, basta remover o nó na lista, liberando o espaço imediatamente. Portanto, não se aplica como desvantagem do encadeamento separado.

---

Conclusão

A desvantagem que realmente se aplica às tabelas de dispersão com encadeamento separado é:

(b) Uso adicional de memória.