Análise Comparativa de Algoritmos de Ordenação

1. Introdução

Este relatório apresenta uma análise detalhada do desempenho de diversos algoritmos de ordenação. Foram implementadas e avaliadas versões tradicionais e otimizadas dos algoritmos: Insertion Sort, Bubble Sort, Selection Sort, Shaker Sort, Shell Sort, Quick Sort e Heap Sort.

A análise foi conduzida utilizando diferentes conjuntos de dados (aleatórios, crescentes e decrescentes) com volumes variados e um conjunto de registros de alunos para observar o comportamento de cada algoritmo em distintos cenários. As métricas de avaliação foram: tempo de execução, número de comparações e número de trocas/movimentações.

2. Conceitos Fundamentais

A Diferença Crucial: Troca vs. Movimentação

Para uma análise de performance precisa, é vital diferenciar "trocas" de "movimentações":

Troca (Swap): É uma operação que envolve a troca de posição entre dois elementos. Tipicamente, requer uma variável auxiliar e resulta em três operações de atribuição (movimentações). Algoritmos como o Bubble Sort e Selection Sort utilizam trocas diretas.
Movimentação (Assignment): Refere-se a uma única operação de atribuição, ou seja, copiar o valor de uma posição para outra. O Insertion Sort, por exemplo, não realiza trocas completas, mas sim "desloca" ou "movimenta" elementos para abrir espaço.

3. Descrição dos Algoritmos e Otimizações

Bubble Sort

Percorre o vetor diversas vezes, comparando pares de elementos adjacentes e os trocando se estiverem fora de ordem. A cada passagem, o maior elemento "flutua" para sua posição final.

Otimização: Utiliza uma flag que verifica se alguma troca foi realizada durante uma passagem. Se nenhuma troca ocorrer, o algoritmo é interrompido, pois o vetor já está ordenado. Isso melhora drasticamente o desempenho no melhor caso (vetor já ordenado), levando a complexidade de O(n²) para O(n).

Shaker Sort

É uma variação do Bubble Sort que percorre o vetor em ambas as direções (ida e volta), movendo o maior e o menor elemento de cada passagem para suas posições corretas.

Otimização: Similar ao Bubble Sort, para a execução se, em um ciclo completo (ida e volta), nenhuma troca for realizada.

Insertion Sort

Constrói o vetor ordenado um elemento por vez, inserindo cada item na posição correta dentro da porção já ordenada à sua esquerda.

Otimização: A implementação padrão já é otimizada para o melhor caso, atingindo complexidade O(n) quando os dados já estão ordenados.

Selection Sort

A cada passo, encontra o menor elemento na parte não ordenada e o troca com o primeiro elemento dessa mesma parte.

Otimização: É inerentemente difícil de otimizar em termos de comparações (sempre O(n²)), pois precisa verificar todos os elementos para achar o mínimo. Não há otimização significativa entre as versões testadas.

Shell Sort

Uma melhoria do Insertion Sort que permite a troca de elementos distantes, ordenando o vetor em intervalos (gaps) que diminuem progressivamente.

Otimização: A performance depende da sequência de gaps. A implementação utiliza a sequência de Knuth (`h = h * 3 + 1`), que oferece um bom desempenho.

Quick Sort

Algoritmo de "dividir para conquistar" que seleciona um pivô e particiona o vetor em dois sub-vetores, aplicando o processo recursivamente.

Otimização: A escolha do pivô é crítica. A versão não otimizada (pivô fixo) leva ao pior caso O(n²) para dados ordenados. A otimização "mediana de três" escolhe o pivô como a mediana entre o primeiro, o meio e o último elemento, tornando o pior caso improvável.

Heap Sort

Utiliza uma estrutura de dados Max Heap. Primeiro, constrói o heap e, em seguida, remove repetidamente o maior elemento (a raiz), colocando-o no final do vetor.

Otimização: Já é um algoritmo eficiente com complexidade garantida de O(n log n) em todos os casos. O processo de construção e extração do heap já é otimizado por natureza.

4. Análise de Desempenho Completa

4.1. Cenário: Dados Aleatórios

Nota sobre a escala dos gráficos: Para que seja possível comparar todos os algoritmos, a escala do eixo Y (vertical) se ajusta automaticamente para incluir o maior valor. Como o desempenho de algoritmos menos eficientes (como Bubble Sort) é ordens de magnitude inferior, suas barras podem se tornar imensas. Isso faz com que as barras dos algoritmos eficientes (Quick Sort, Heap Sort) pareçam minúsculas em comparação, destacando a enorme diferença de performance entre eles.

Tempo de Execução (ms)

Nº de Trocas

Nº de Movimentações

4.2. Cenário: Dados Crescentes

Nota sobre a escala: Os valores zerados para tempo e movimentações, especialmente no gráfico de 500 elementos, são esperados. Isso ocorre porque, com um vetor já ordenado (o melhor caso), as operações são extremamente rápidas (muitas vezes abaixo de 1ms) e os algoritmos otimizados não precisam realizar movimentações de dados. A escala se ajusta para os valores maiores do Selection Sort, o que reforça a eficiência dos outros métodos neste cenário. O Quick Sort não otimizado falha com 50.000 elementos (ausência de barra), enquanto sua versão otimizada, junto com o Heap Sort, mostra um desempenho estável.

Tempo de Execução (ms)

Nº de Trocas

Nº de Movimentações

4.3. Cenário: Dados Decrescentes

Nota sobre a escala: Este cenário destaca a fraqueza dos algoritmos O(n²). Suas barras de desempenho são tão grandes que dominam a escala do gráfico, fazendo com que os algoritmos O(n log n) pareçam ter um desempenho próximo de zero, o que ilustra sua superioridade. O Quick Sort não otimizado novamente falha com 50.000 elementos, um problema que a versão otimizada resolve com eficácia.

Tempo de Execução (ms)

Nº de Trocas

Nº de Movimentações

4.4. Cenário: Registros de Alunos

Ao ordenar 1.000 registros, a diferença está no número de comparações e trocas/movimentações. Algoritmos O(n log n) são mais eficientes. Este teste também avalia a estabilidade: um algoritmo estável mantém a ordem relativa de elementos com chaves de ordenação iguais, o que é importante em cadastros.

5. Caso Especial: O Estouro de Pilha do Quick Sort

Um dos resultados mais notáveis foi o estouro da pilha de recursão (Stack Overflow) na versão não otimizada do Quick Sort ao ordenar 50.000 elementos em ordem crescente ou decrescente. Isso está refletido nos gráficos pela ausência da barra correspondente.

Por que isso acontece? A implementação padrão, ao escolher um pivô fixo, entra em seu pior caso. Isso cria uma árvore de recursão com profundidade `n`, excedendo a memória da pilha de execução. A solução para este problema não foi aumentar a memória da pilha (o que pode ser inviável), mas sim corrigir a causa raiz no algoritmo. A versão otimizada, usando "mediana de três", evita a criação de uma árvore de recursão desbalanceada, garantindo que o limite da pilha não seja atingido.

6. Conclusão

A análise confirma a teoria: otimizações têm um impacto profundo no desempenho. Para dados aleatórios de grande volume, Quick Sort (otimizado), Heap Sort e Shell Sort são as escolhas mais robustas. Para dados que já estão parcial ou totalmente ordenados, o Insertion Sort pode ser surpreendentemente eficaz. A escolha do algoritmo correto depende fundamentalmente da natureza dos dados.