Faça uma comparação entre todos os métodos de ordenação estudados em aula com relação a estabilidade (preservar ordem lexicográfica), ordem de complexidade levando em consideração comparações e movimentações.

Passo 1

O exercício pede comparar todos os algoritmos de ordenação vistos em aula com relação a dois critérios: estabilidade (se preservam a ordem de elementos iguais) e ordem de complexidade para número de comparações e número de movimentações (trocas ou deslocamentos). Vamos focar nos seis métodos principais: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort e Heap Sort.

Passo 2

Estabilidade é a propriedade que garante que, quando dois elementos são iguais segundo a chave de ordenação, a ordem relativa em que eles aparecem no input seja mantida no output. Movimentações são as operações de troca ou deslocamento de elementos na estrutura de dados, e comparações são as vezes que comparamos chaves de dois elementos durante o processo.

Passo 3

Analisando os métodos simples (quadráticos):
  • Bubble Sort: é estável; faz Theta(n^2) comparações e até Theta(n^2) trocas no pior caso.
  • Selection Sort: não é estável; faz Theta(n^2) comparações e exatamente Theta(n) trocas (um por iteração).
  • Insertion Sort: é estável; faz Theta(n^2) comparações e Theta(n^2) deslocamentos no pior caso, mas no melhor caso (quase ordenado) chega a Theta(n) comparações e movimentações.

Passo 4

Analisando os métodos eficientes ( nlog n):
  • Merge Sort: é estável (quando implementado corretamente); faz Theta(nlog n) comparações e Theta(nlog n) movimentações (na prática Theta(n) por nível de recursão, totalizando Theta(nlog n)).
  • Quick Sort: não é estável na versão padrão; faz Theta(nlog n) comparações e Theta(nlog n) trocas no caso médio, mas pode degradar para Theta(n^2) comparações e trocas no pior caso (quando o pivô é sempre o menor ou maior elemento).
  • Heap Sort: não é estável; faz Theta(nlog n) comparações e Theta(nlog n) movimentações tanto no caso médio quanto no pior caso.

Passo 5

Concluímos que os algoritmos estáveis são Bubble Sort, Insertion Sort e Merge Sort. Selection Sort, Quick Sort e Heap Sort não garantem estabilidade. Em termos de complexidade de comparações e movimentações, os três primeiros são Theta(n^2) no pior caso, enquanto Merge, Quick (médio) e Heap têm complexidade Theta(nlog n) no número de comparações e movimentações, sendo que Quick Sort pode chegar a Theta(n^2) no pior caso.

Resposta

Resumo dos algoritmos:
  • Bubble Sort: estável; Theta(n^2) comparações; Theta(n^2) movimentações.
  • Selection Sort: instável; Theta(n^2) comparações; Theta(n) movimentações.
  • Insertion Sort: estável; Theta(n^2) comparações; Theta(n^2) movimentações ( Theta(n) no melhor caso).
  • Merge Sort: estável; Theta(nlog n) comparações; Theta(nlog n) movimentações.
  • Quick Sort: instável; Theta(nlog n) comparações e movimentações no caso médio, Theta(n^2) no pior caso.
  • Heap Sort: instável; Theta(nlog n) comparações; Theta(nlog n) movimentações.

Exercícios relacionados