Algoritmos e Estrutura de Dados · UFRRJ · 2023 | Questão sqc-qg045236

GabaritoC — bubblesort é considerado um algoritmo estável, apresentando uma complexidade de O(n²) comparações no pior caso.

Algoritmos de ordenação: estabilidade e complexidade

Gabarito: letra C. O bubblesort é um algoritmo estável (preserva a ordem relativa de elementos iguais) e sua complexidade no pior caso é O(n²) comparações. As demais alternativas erram ao atribuir estabilidade ou complexidade a outros algoritmos.

A banca testa o conhecimento das características fundamentais dos principais algoritmos de ordenação: estabilidade, complexidade e estratégia de projeto. Vamos analisar cada alternativa.

Algoritmo	Estabilidade	Complexidade (melhor caso)	Complexidade (pior caso)	Estratégia
Heapsort	Não estável	O(n log n)	O(n log n)	Heap (árvore binária)
Mergesort	Estável	O(n log n)	O(n log n)	Divisão e conquista
Bubblesort	Estável	O(n)	O(n²)	Comparação adjacente
Insertion sort	Estável	O(n)	O(n²)	Inserção em lista ordenada
Quicksort	Não estável	O(n log n)	O(n²)	Divisão e conquista (partição)

Algoritmos de ordenação

1Estáveis
- Bubblesort
- Mergesort
- Insertion sort
2Instáveis
- Heapsort
- Quicksort
3Complexidade
- O(n²) pior caso
  - Bubblesort
  - Insertion sort
- O(n log n) pior caso
  - Mergesort
  - Heapsort
  - Quicksort

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

O heapsort não é estável: durante a extração do máximo e reconstrução do heap, elementos com chaves iguais podem ter sua ordem relativa alterada. Além disso, sua estratégia não é divisão e conquista, mas sim o uso de uma estrutura de dados heap (árvore binária quase completa). A complexidade do heapsort é O(n log n) no pior caso, melhor caso e caso médio.

Alternativa B — ❌ Incorreta

O mergesort é estável (desde que a intercalação preserve a ordem de elementos iguais), e sua complexidade no melhor caso é O(n log n), não O(n²). A complexidade O(n²) no melhor caso é característica de algoritmos como bubblesort (na versão ingênua) ou insertion sort (no pior caso).

Alternativa C — ✅ Correta ⟵ GABARITO

O bubblesort é estável (elementos iguais não trocam de posição, pois a comparação só ocorre quando o elemento da esquerda é maior que o da direita). Sua complexidade no pior caso (lista invertida) é O(n²) comparações, pois para cada um dos n elementos percorre-se a lista até o final, com n-1, n-2, … 1 comparações, totalizando n(n-1)/2. No melhor caso (lista já ordenada), uma versão otimizada pode parar após uma varredura, resultando em O(n).

Alternativa D — ❌ Incorreta

O insertion sort é estável (insere cada elemento na posição correta sem ultrapassar elementos iguais). Sua complexidade no pior caso (lista invertida) é O(n²), não O(n). O(n) é a complexidade do melhor caso (lista já ordenada). A alternativa confunde o melhor caso com o pior caso.

Alternativa E — ❌ Incorreta

O quicksort não é estável (durante a partição, elementos iguais podem ser trocados). Sua estratégia é divisão e conquista, não "inserção de dados em lista". A afirmação troca a estratégia e o atributo de estabilidade.

PEGA ESSA DICA!

Para memorizar estabilidade, lembre-se: algoritmos que trocam elementos adjacentes ou inserem em ordem (bubble, insertion, merge) tendem a ser estáveis, enquanto os que fazem trocas distantes (quicksort, heapsort) são instáveis. O mergesort é uma exceção que é estável apesar de não ser adjacente, porque a intercalação pode preservar a ordem relativa.

Gabarito: letra C — apenas o bubblesort combina estabilidade e complexidade O(n²) no pior caso conforme descrito.