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
comparações e até trocas no pior caso. - Selection Sort: não é estável; faz
comparações e exatamente trocas (um por iteração). - Insertion Sort: é estável; faz
comparações e deslocamentos no pior caso, mas no melhor caso (quase ordenado) chega a comparações e movimentações.
Passo 4
Analisando os métodos eficientes (
):
- Merge Sort: é estável (quando implementado corretamente); faz
comparações e movimentações (na prática por nível de recursão, totalizando ). - Quick Sort: não é estável na versão padrão; faz
comparações e trocas no caso médio, mas pode degradar para comparações e trocas no pior caso (quando o pivô é sempre o menor ou maior elemento). - Heap Sort: não é estável; faz
comparações e 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
no pior caso, enquanto Merge, Quick (médio) e Heap têm complexidade
no número de comparações e movimentações, sendo que Quick Sort pode chegar a
no pior caso.
Resposta
Resumo dos algoritmos:
- Bubble Sort: estável;
comparações; movimentações. - Selection Sort: instável;
comparações; movimentações. - Insertion Sort: estável;
comparações; movimentações ( no melhor caso). - Merge Sort: estável;
comparações; movimentações. - Quick Sort: instável;
comparações e movimentações no caso médio, no pior caso. - Heap Sort: instável;
comparações; movimentações.