Algoritmos de ordenação têm comportamentos surpreendentes dependendo dos dados de entrada. Insertion Sort (O(n²)) pode vencer Quick Sort (O(n log n)) em arrays quase ordenados. Radix Sort ordena sem fazer nenhuma comparação entre elementos. Selection Sort sempre faz o mesmo número de comparações independente da ordem inicial. Esses 7 experimentos revelam como complexidade algorítmica funciona na prática, não apenas na teoria.
Se você acha que algoritmos "melhores" sempre vencem, prepare-se para surpresas. A complexidade algorítmica não é uma hierarquia simples — o contexto dos dados importa tanto quanto a notação Big-O.
Neste artigo, você vai descobrir 7 fenômenos contra-intuitivos que pode ver acontecendo ao vivo no Sorting Arena. Cada experimento vem com instruções passo a passo para você replicar e entender por que isso acontece.
🐌 Experimento 1: O Custo Dramático do O(n²)
🧪 Como testar
- Configure Tamanho do Array para
50 - Selecione Ordem Inicial como
Aleatório - Ative Bubble Sort e Merge Sort
- Clique em Iniciar e observe
- Agora mude para
200 elementose repita
Com 50 elementos, a diferença é perceptível mas não chocante. Com 200 elementos, Bubble Sort fica dramaticamente para trás — Merge Sort termina em segundos enquanto Bubble Sort ainda está processando. O contador de operações mostra Bubble Sort fazendo ~40.000 ops vs ~3.000 do Merge Sort.
Por que isso acontece: Algoritmos quadráticos têm crescimento exponencial. Dobrar o tamanho do array quadruplica o tempo de execução. Com 200 elementos, você vê essa diferença explodir visualmente.
Segundo pesquisas de Donald Knuth em The Art of Computer Programming (1997), em um computador típico, Bubble Sort processa cerca de 500.000 elementos por segundo. Para 100.000 elementos, isso significa 200 segundos (mais de 3 minutos) enquanto Merge Sort levaria menos de 1 segundo.
🪤 Experimento 2: Quick Sort no Pior Caso
🧪 Como testar
- Configure Tamanho do Array para
150 - Selecione Ordem Inicial como
Invertido - Ative Quick Sort e Merge Sort
- Clique em Iniciar
- Compare com modo
Aleatório
Em modo Aleatório, Quick Sort é rápido e competitivo. Em modo Invertido, Quick Sort degrada significativamente — pode até ficar mais lento que Merge Sort. O número de operações sobe dramaticamente.
Por que isso acontece: Quick Sort escolhe um pivô e particiona o array em "menores" e "maiores". Com arrays já ordenados ou invertidos, e usando pivô simples (último elemento), todas as partições ficam desbalanceadas — uma vazia e outra com n-1 elementos. Isso degrada de O(n log n) para O(n²).
Implementações modernas (como std::sort em C++) usam introsort: começam com Quick Sort mas detectam degradação e trocam para Heap Sort automaticamente.
⚡ Experimento 3: Insertion Sort Vencendo Quick Sort
🧪 Como testar
- Configure Tamanho do Array para
100 - Selecione Ordem Inicial como
Quase Ordenado - Ative Insertion Sort e Quick Sort
- Clique em Iniciar
Insertion Sort pode terminar em 1º lugar! O contador de operações mostra Insertion Sort fazendo muito menos operações que o esperado — às vezes menos de 1.000 ops para 100 elementos.
Por que isso acontece: Insertion Sort é adaptativo — detecta quando elementos já estão próximos da posição correta e faz menos movimentos. Em arrays quase ordenados, pode atingir O(n) no melhor caso, enquanto Quick Sort sempre faz O(n log n) independente da ordem inicial.
É por isso que linguagens modernas usam Timsort (Python, JavaScript): um híbrido que usa Insertion Sort para subgrupos pequenos ou quase ordenados, e Merge Sort para o resto.
🧊 Experimento 4: Selection Sort Sempre Igual
🧪 Como testar
- Ative Selection Sort nos parâmetros
- Configure Tamanho do Array para
100 - Rode com
Aleatórioe anote o número de comparações - Rode novamente com
Quase Ordenado - Compare os contadores
O número de comparações é praticamente idêntico nos dois modos (~4.950 para 100 elementos). Apenas o número de trocas varia.
Por que isso acontece: Selection Sort não é adaptativo. Ele sempre procura o menor elemento em toda a parte não ordenada, mesmo que já esteja no lugar certo. Para n elementos, sempre faz exatamente n(n-1)/2 comparações — independente de aleatório, ordenado ou invertido.
Isso torna Selection Sort previsível mas ineficiente. Nunca se beneficia de dados parcialmente ordenados.
📊 Experimento 5: Poucos Valores Únicos
🧪 Como testar
- Configure Tamanho do Array para
150 - Selecione Ordem Inicial como
Poucos Únicos - Ative vários algoritmos: Bubble, Insertion, Merge, Quick
- Clique em Iniciar
Alguns algoritmos lidam melhor com duplicados que outros. Observe como o número de trocas varia — algoritmos estáveis fazem menos trocas desnecessárias.
Por que isso acontece: Quando há muitos valores iguais, algoritmos estáveis (que mantêm ordem relativa de elementos iguais) se beneficiam por não precisar trocar elementos de mesmo valor. Merge Sort e Insertion Sort são estáveis; Quick Sort e Heap Sort não são.
Variantes modernas de Quick Sort usam 3-way partitioning (Dutch National Flag) para otimizar casos com muitos duplicados, separando em três grupos: menores, iguais e maiores que o pivô.
🐚 Experimento 6: Shell Sort e o Poder dos Gaps
🧪 Como testar
- Ative Shell Sort e Insertion Sort nos parâmetros
- Configure Tamanho do Array para
150 - Selecione Ordem Inicial como
Aleatório - Clique em Iniciar
Shell Sort termina muito mais rápido que Insertion Sort, com significativamente menos operações — às vezes metade das operações ou menos.
Por que isso acontece: Shell Sort é uma evolução inteligente do Insertion Sort. Em vez de comparar apenas vizinhos, ele compara elementos separados por um gap (distância) que vai diminuindo (ex: 75 → 37 → 18 → 9 → 4 → 2 → 1).
Isso permite que elementos façam "saltos grandes" para se aproximarem da posição final, pré-ordenando subgrupos distantes. Quando o gap chega a 1 (virando Insertion Sort normal), o array já está quase ordenado, tornando a passada final muito rápida.
A complexidade de Shell Sort depende da sequência de gaps usada — pode variar de O(n log n) até O(n^1.5) dependendo da implementação.
🔢 Experimento 7: Radix Sort — Zero Comparações
🧪 Como testar
- Ative Radix Sort e outros algoritmos nos parâmetros
- Configure Tamanho do Array para
200 - Selecione Ordem Inicial como
Aleatório - Clique em Iniciar
- Observe o contador de comparações do Radix Sort
O contador de comparações do Radix Sort fica em 0 enquanto os outros sobem aos milhares! Mesmo assim, Radix Sort termina rapidamente.
Por que isso acontece: Radix Sort é fundamentalmente diferente — ele não compara elementos entre si. Em vez disso, ordena dígito por dígito, do menos significativo ao mais significativo, usando counting sort como sub-rotina.
Para cada dígito (0-9), ele conta quantos números têm aquele dígito naquela posição e reorganiza baseado nessas contagens. Como não precisa comparar valores, o contador fica em 0.
Radix Sort tem complexidade O(n·k), onde k é o número de dígitos. Para números de até 3 dígitos, é extremamente rápido. Mas só funciona com dados que podem ser divididos em dígitos (números inteiros, strings de tamanho fixo).
"Radix Sort prova que nem todo problema de ordenação precisa ser resolvido por comparações. Pensar fora da caixa da comparação pode levar a algoritmos mais eficientes para tipos específicos de dados." — Robert Sedgewick, Algorithms (4ª ed.)
🔬 Rode Todos os Experimentos Agora
Veja esses fenômenos acontecendo ao vivo. Ajuste parâmetros, compare 8 algoritmos simultaneamente e descubra novos padrões.
Abrir Sorting ArenaPerguntas Frequentes
Insertion Sort pode realmente ser mais rápido que Quick Sort?
Sim! Em arrays quase ordenados, Insertion Sort pode vencer Quick Sort. Insertion Sort é adaptativo (O(n) no melhor caso), enquanto Quick Sort sempre faz O(n log n) operações independente da ordem inicial. Use ordem "Quase Ordenado" no Sorting Arena para ver isso acontecer.
Como Radix Sort ordena sem comparar elementos?
Radix Sort ordena dígito por dígito usando counting sort como sub-rotina. Ele conta quantos números têm cada dígito (0-9) em cada posição e reorganiza baseado nessas contagens. Como não compara valores entre si, o contador de comparações fica em 0.
Por que Selection Sort sempre faz o mesmo número de comparações?
Selection Sort não é adaptativo. Ele sempre procura o menor elemento em toda a parte não ordenada do array, independente de já estar em posição correta. Isso resulta em exatamente n(n-1)/2 comparações em todos os casos — aleatório, quase ordenado ou invertido.
O que torna Shell Sort mais rápido que Insertion Sort?
Shell Sort compara elementos separados por gaps (distâncias) que vão diminuindo, pré-ordenando subgrupos distantes do array. Isso permite que elementos façam "saltos grandes" para se aproximarem da posição final, reduzindo drasticamente o número de trocas comparado ao Insertion Sort que só move vizinhos.
Como posso rodar esses experimentos?
Acesse o Sorting Arena em https://simulabz.com/games/10_algoritmos_de_sorting/sorting-arena.html. Selecione os algoritmos que quer comparar, escolha o tamanho do array e ordem inicial, e clique em Iniciar. Todas as instruções específicas de cada experimento estão no artigo.