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
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:
-O0 e -O3 para 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.
{% embed https://github.com/Bernardo-Lebron/simple_sort_algorithms %}
Trabalho prático da disciplina de Algoritmos e Estruturas de Dados I — CEFET-MG Campus V, Divinópolis. Orientação: Prof. Michel Pires.