Sorting Wars: Benchmarking Selection, Insertion, Gnome e Bubble Sort em 5 Linguagens

Bernardo Lebron — Sat, 16 May 2026 04:44:08 +0000

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: -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.

Bernardo-Lebron / simple_sort_algorithms

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…

View on GitHub

Trabalho prático da disciplina de Algoritmos e Estruturas de Dados I — CEFET-MG Campus V, Divinópolis. Orientação: Prof. Michel Pires.

DEV Community: Bernardo Lebron

Sorting Wars: Benchmarking Selection, Insertion, Gnome e Bubble Sort em 5 Linguagens

🤔 Por que estudar algoritmos O(n²) em 2025?

📐 Os Algoritmos

Selection Sort — O inflexível

Insertion Sort — O adaptativo

Gnome Sort — O excêntrico

Bubble Sort — O clássico (com parada antecipada)

🧪 Metodologia

📊 Resultados — Selection Sort

📊 Resultados — Insertion Sort

📊 Resultados — Gnome Sort

📊 Resultados — Bubble Sort

🔑 Principais Aprendizados

1. Otimização de compilador importa muito mais do que parece

2. Adaptatividade é real e mensurável

3. Python tem overhead estrutural, não só de interpretador

4. JIT pode superar código estático em padrões repetitivos

5. A hierarquia não é fixa

🔬 Conclusão

Bernardo-Lebron / simple_sort_algorithms

Comparativo de Desempenho: Algoritmos de Ordenação Simples

📋 Sumário

🤔 1. O que são Métodos de Ordenação?