Questão de Algoritmos e Estrutura de Dados — Algoritmos — UFLA 2018

Método de ordenação Bolha (Bubble Sort)

Gabarito: letra C. O vetor [10, 8, 7, 0] ordenado em ordem crescente pelo Bubble Sort ingênuo resulta em exatamente 6 comparações e 6 trocas. Simulemos passo a passo.

O vetor inicial é [10, 8, 7, 0]. O algoritmo percorre repetidamente o vetor, comparando pares adjacentes e trocando se estiverem na ordem errada. A cada passagem, o maior elemento não ordenado "flutua" para o final.

Passagem 1 (i=0, j=0 até 2):

• Comparação 1: 10 > 8? Sim → troca: [8, 10, 7, 0] (1 troca)

• Comparação 2: 10 > 7? Sim → troca: [8, 7, 10, 0] (2 trocas)

• Comparação 3: 10 > 0? Sim → troca: [8, 7, 0, 10] (3 trocas)

Comparações: 3, Trocas: 3

Passagem 2 (i=1, j=0 até 1):

• Comparação 4: 8 > 7? Sim → troca: [7, 8, 0, 10] (4 trocas)

• Comparação 5: 8 > 0? Sim → troca: [7, 0, 8, 10] (5 trocas)

Comparações: 2 (total 5), Trocas: 2 (total 5)

Passagem 3 (i=2, j=0 até 0):

• Comparação 6: 7 > 0? Sim → troca: [0, 7, 8, 10] (6 trocas)

Comparações: 1 (total 6), Trocas: 1 (total 6)

Após a terceira passagem, o vetor está ordenado. Total: 6 comparações e 6 trocas.

Alternativa A — ❌ Incorreta

Afirma 6 comparações e 4 trocas. O número de trocas está subestimado: foram 6, não 4.

Alternativa B — ❌ Incorreta

Afirma 8 comparações e 6 trocas. As comparações são 6 (n*(n-1)/2 = 6) e não 8.

Alternativa C — ✅ Correta ⟵ GABARITO

6 comparações e 6 trocas, conforme simulação.

Alternativa D — ❌ Incorreta

Afirma 8 comparações e 8 trocas. Ambos os números estão inflados.

Gabarito: letra C