Algoritmos quadráticos são lentos — isso todo mundo sabe. Mas o quão lentos? E a linguagem escolhida importa mais do que o algoritmo em si? Foi exatamente isso que nossa turma de Algoritmos e Estruturas de Dados I do CEFET-MG decidiu testar empiricamente.
Implementamos Selection Sort, Insertion Sort, Gnome Sort e Bubble Sort em C, C++, Rust, JavaScript e Python, rodamos benchmarks com até 1 milhão de elementos e coletamos os dados. Esse post resume o que encontramos — incluindo alguns resultados que nos surpreenderam bastante.
🤔 Por que estudar algoritmos O(n²) em 2025?
Antes de mergulhar nos números, vale responder a pergunta óbvia. Três razões principais:
- Didática — a lógica é direta, ideal para aprender análise de complexidade e invariantes de laço.
-
Entradas pequenas — para
N ≤ ~50, o overhead reduzido pode torná-los mais rápidos que algoritmos sofisticados. - Adaptatividade — Insertion Sort e Bubble Sort com parada antecipada chegam a O(n) em entradas quase ordenadas. É por isso que o TimSort (usado em Python e Java) usa Insertion Sort internamente para subconjuntos pequenos.
📐 Os Algoritmos
Selection Sort — O inflexível
Seleciona o mínimo do subarray não ordenado e o move para a posição correta com uma única troca.
PARA i DE 0 ATE N - 2 FACA
MIN_IDX <- i
PARA j DE i + 1 ATE N - 1 FACA
SE VETOR[j] < VETOR[MIN_IDX] ENTAO
MIN_IDX <- j
SE MIN_IDX != i ENTAO
TROCA VETOR[i] COM VETOR[MIN_IDX]
Característica marcante: sempre realiza exatamente n(n-1)/2 comparações, independente da entrada. Não existe melhor caso em comparações — é Θ(n²) em todos os cenários.
| Caso | Comparações | Complexidade |
|---|---|---|
| Melhor (ordenado) | n(n−1)/2 | O(n²) |
| Médio (aleatório) | n(n−1)/2 | O(n²) |
| Pior (invertido) | n(n−1)/2 | O(n²) |
✅ In-place · ❌ Não estável · ❌ Não adaptativo
Insertion Sort — O adaptativo
Mantém um subarray ordenado à esquerda e insere cada novo elemento na posição correta via shifting.
PARA i DE 1 ATE N - 1 FACA
CHAVE <- VETOR[i]
j <- i - 1
ENQUANTO j >= 0 E VETOR[j] > CHAVE FACA
VETOR[j + 1] <- VETOR[j]
j <- j - 1
VETOR[j + 1] <- CHAVE
Em entradas já ordenadas, o laço interno nunca executa: complexidade O(n) no melhor caso. Isso ficou claro nos nossos dados — até 10⁶ elementos, o cenário crescente terminou em microssegundos.
| Caso | Comparações | Complexidade |
|---|---|---|
| Melhor (ordenado) | n − 1 | O(n) |
| Médio (aleatório) | n(n−1)/4 | O(n²) |
| Pior (invertido) | n(n−1)/2 | O(n²) |
✅ In-place · ✅ Estável · ✅ Adaptativo
Gnome Sort — O excêntrico
Opera como um "gnomo organizando vasos": avança comparando adjacentes, e ao encontrar desordem, troca e recua uma posição.
INDICE <- 0
ENQUANTO INDICE < N FACA
SE INDICE = 0 OU VETOR[INDICE] >= VETOR[INDICE - 1] ENTAO
INDICE <- INDICE + 1
SENAO
TROCA VETOR[INDICE] COM VETOR[INDICE - 1]
INDICE <- INDICE - 1
Funcionalmente equivalente a um Insertion Sort por trocas — mas com movimento local em vez de shifting. Também adaptativo: O(n) no melhor caso.
| Caso | Comparações | Complexidade |
|---|---|---|
| Melhor (ordenado) | n − 1 | O(n) |
| Médio (aleatório) | (A DEPENDER) | O(n²) |
| Pior (invertido) | n(n−1)/2 | O(n²) |
✅ In-place · ✅ Estável · ✅ Adaptativo
Bubble Sort — O clássico (com parada antecipada)
Realiza passagens comparando pares adjacentes. A variável swapped permite encerramento antecipado quando o vetor já está ordenado.
PARA i DE 0 ATE N - 1 FACA
SWAPPED <- FALSO
PARA j DE 0 ATE N - i - 2 FACA
SE VETOR[j] > VETOR[j + 1] ENTAO
TROCA VETOR[j] COM VETOR[j+1]
SWAPPED <- VERDADEIRO
SE SWAPPED = FALSO ENTAO
RETORNE // Encerramento antecipado
| Caso | Comparações | Complexidade |
|---|---|---|
| Melhor (ordenado) | n − 1 | O(n) |
| Médio (aleatório) | n(n−1)/4 | O(n²) |
| Pior (invertido) | n(n−1)/2 | O(n²) |
✅ In-place · ✅ Estável · ✅ Adaptativo (com parada antecipada)
🧪 Metodologia
- Tamanhos de entrada: N ∈ { 10², 10³, 10⁴, 10⁵, 10⁶ }
- Cenários: crescente (melhor caso), aleatório (caso médio), decrescente (pior caso)
- Repetições: 5 execuções; média das 3 centrais (descartando menor e maior)
-
Otimizações testadas:
-O0e-O3para C/C++/Rust - Medição: apenas tempo de ordenação (I/O descartado)
Cada linguagem usou sua estrutura de dados nativa:
| Linguagem | Estrutura | Tipo |
|---|---|---|
| C |
double[] com malloc
|
double 64-bit |
| C++ | std::vector<double> |
double 64-bit |
| Rust | Vec<f64> |
f64 64-bit |
| JavaScript |
Array (V8 float64) |
Number |
| Python |
list (refs a PyObject) |
float |
📊 Resultados — Selection Sort
O Selection Sort foi o mais previsível: tempos quase idênticos nos três cenários, confirmando a não-adaptatividade.
N = 10⁵ — tempo em segundos (-O3 / otimização máxima)
| Linguagem | Crescente (s) | Aleatório (s) | Decrescente (s) |
|---|---|---|---|
| C (-O3) | 2.0500 | 3.5188 | 1.9618 |
| C++ (-O3) | 2.1247 | 3.5188 | 1.9089 |
| Rust (-O3) | 2.3265 | 4.2560 | 2.1320 |
| JavaScript (V8) | 3.5835 | 6.6564 | 3.5851 |
| Python | 93.164 | 164.890 | 98.378 |
Python para N = 10⁶ foi descartado — tempo estimado superior a 10 horas.
Hierarquia: C -O3 ≈ C++ -O3 < Rust < JavaScript ≪ Python
📊 Resultados — Insertion Sort
Aqui a adaptatividade brilhou. No cenário crescente com N = 10⁶, todas as linguagens terminaram em menos de 12 ms. Já no cenário decrescente, o pior caso quadrático foi brutal:
N = 10⁵ — tempo em segundos (-O3 / otimização máxima)
| Linguagem | Crescente (s) | Aleatório (s) | Decrescente (s) |
|---|---|---|---|
| C (-O3) | 0.000055 | 0.615683 | 1.188966 |
| C++ (-O3) | 0.0000634 | 0.587483 | 1.183000 |
| Rust (-O3) | 0.000079 | 0.897895 | 1.774292 |
| JavaScript (V8) | 0.000809 | 1.525250 | 3.033301 |
| Python | 0.005321 | 136.295 | 226.560 |
Para N = 10⁶ no pior caso sem otimização, C++ chegou a 3670 s (~1 hora). Com
-O3, caiu para 119 s — speedup de ~30×.
📊 Resultados — Gnome Sort
O Gnome Sort trouxe a maior surpresa da série: Rust superou C e C++ no caso médio.
N = 10⁵ — tempo em segundos (-O3 / otimização máxima)
| Linguagem | Crescente (s) | Aleatório (s) | Decrescente (s) |
|---|---|---|---|
| C (-O3) | 0.000179 | 15.19068 | 28.90668 |
| C++ (-O3) | 0.000159 | 13.96807 | 28.25787 |
| Rust (-O3) | 0.000049 | 3.94810 | 8.27646 |
| JavaScript (V8) | 0.001584 | 13.90908 | 27.45163 |
| Python | 0.019030 | 21.28324 | 257.00624 |
Por quê? O padrão de acesso do Gnome Sort — muitos acessos locais e trocas adjacentes — se beneficia especialmente das otimizações do compilador LLVM (backend do Rust), que gera código de swap em registrador sem acesso intermediário à memória.
📊 Resultados — Bubble Sort
O Bubble Sort entregou o resultado mais inesperado de todo o projeto:
N = 10⁵ — tempo em segundos (-O3 / otimização máxima)
| Linguagem | Crescente (s) | Aleatório (s) | Decrescente (s) |
|---|---|---|---|
| C (-O3) | 0.000042 | 20.489569 | 23.568626 |
| C++ (-O3) | 0.000045 | 21.165759 | 23.919268 |
| Rust (-O3) | 0.000051 | 13.513529 | 9.231813 |
| JavaScript (V8) | 0.001753 | 15.012168 | 6.905683 🎉 |
| Python | 0.003504 | 312.509064 | 403.412438 |
JavaScript bateu C e C++ no pior caso. O motor V8 identificou o padrão repetitivo de trocas adjacentes e gerou código de máquina altamente especializado via JIT. É um caso raro onde a compilação dinâmica supera a compilação estática.
🔑 Principais Aprendizados
1. Otimização de compilador importa muito mais do que parece
O impacto de -O3 vs -O0 para Rust no Bubble Sort chegou a 23× para N = 10⁴. Em modo debug, o Rust mantém verificações de bounds checking em todo acesso ao array — correto para desenvolvimento, devastador para performance.
2. Adaptatividade é real e mensurável
Insertion Sort com N = 10⁶ no cenário crescente: < 1 ms. No cenário decrescente: até 3670 s (sem otimização). Isso é uma diferença de mais de 10 ordens de magnitude no número de operações.
3. Python tem overhead estrutural, não só de interpretador
A list do Python armazena referências a objetos PyObject — cada acesso e comparação envolve uma indireção de ponteiro. Isso multiplica o custo por operação mesmo para tipos simples como int e float.
4. JIT pode superar código estático em padrões repetitivos
O V8 observa o comportamento em runtime e especializa o código gerado. Para algoritmos com padrões de acesso altamente previsíveis (como Bubble Sort), isso pode ser mais eficiente que otimizações estáticas conservadoras de um compilador AOT.
5. A hierarquia não é fixa
A ordem geral foi C ≈ C++ < Rust < JS < Python, mas exceções importantes existem — Rust venceu todos no Gnome Sort, JS venceu todos no Bubble Sort em pior caso. O melhor resultado depende do algoritmo, tamanho de entrada e padrão de acesso.
🔬 Conclusão
Algoritmos simples ensinam mais do que complexidade assintótica. Ensinam sobre a relação entre padrões de acesso à memória e otimizações de compilador, sobre como compilação JIT funciona na prática, e sobre por que constantes importam tanto quanto expoentes para tamanhos reais de entrada.
Se você quiser explorar o código completo, estrutura de Makefiles, geradores de dataset e scripts de benchmark, o repositório está público no GitHub.
Comparativo de Desempenho: Algoritmos de Ordenação Simples
Este repositório contém um ambiente de benchmarking experimental para analisar e comparar o desempenho de quatro algoritmos de ordenação simples: Selection Sort, Insertion Sort, Gnome Sort e Bubble Sort.
Os algoritmos são implementados em múltiplas linguagens de programação e avaliados sob diferentes tamanhos de entrada e cenários de ordenação, com o objetivo de verificar empiricamente as previsões teóricas de complexidade computacional.
Trabalho prático da disciplina de Algoritmos e Estruturas de Dados I CEFET-MG — Campus V, Divinópolis
📋 Sumário
- O que são Métodos de Ordenação?
- Contextualização dos Algoritmos Simples
- Objetivos
- Estrutura do Projeto
- Algoritmos Analisados
- 5.1. Selection Sort
- 5.2. Insertion Sort
- 5.3. Gnome Sort
- 5.4. Bubble Sort
- Metodologia Experimental
- Equipe e Colaboradores
🤔 1. O que são Métodos de Ordenação?
Métodos de ordenação são algoritmos computacionais utilizados para reorganizar os elementos de uma estrutura de dados segundo uma ordem determinada…
Trabalho prático da disciplina de Algoritmos e Estruturas de Dados I — CEFET-MG Campus V, Divinópolis. Orientação: Prof. Michel Pires.