Quick Sort costuma ser chamado de algoritmo rápido, mas essa reputação tem asterisco. No caso médio ele roda em O(n log n); no pior caso, com pivô mal escolhido, ele empata com o Selection Sort em O(n²). Entender essa distinção é o que separa usar o .sort() de saber quando ele não basta.
O que é Quick Sort e por que ele importa antes do .sort()
Quick Sort é um algoritmo de ordenação por divisão e conquista que escolhe um pivô, particiona o array em elementos menores e maiores, e aplica recursão nos subarrays. O caso médio é O(n log n) e o pior caso é O(n²). Ele importa porque funções nativas como Array.prototype.sort em JavaScript e sorted() em Python escondem qual algoritmo roda por trás — e escondem também o custo real quando a lista cresce para milhões de itens.
A pergunta que a engenheira Fernanda Kipper levanta em uma live de 27 de agosto de 2026 é direta: quando você chama o sort nativo, qual algoritmo está sendo executado e até que ponto ele continua eficiente para o seu caso de uso? A resposta não é um nome único, porque a escolha varia por linguagem, versão e motor de execução.
Segundo a especificação ECMAScript, o comportamento de Array.prototype.sort exige estabilidade, mas não obriga um algoritmo específico — na prática os motores escolhem entre TimSort e variantes híbridas como a Pattern-Defeating QuickSort. Já a documentação do CPython observa que o sorted() usa TimSort, um híbrido derivado de merge sort e insertion sort, e por isso é estável. Saber disso muda a decisão: o nativo costuma ser a escolha certa, mas o Quick Sort explica o modelo mental que sustenta esse julgamento.
Selection Sort: como o O(n²) aparece em loops aninhados
Selection Sort funciona encontrando repetidamente o maior (ou menor) elemento restante e movendo-o para o final da lista ordenada. Cada busca custa O(n), e você repete essa busca n vezes — daí o O(n²).
A notação Big O descreve como o tempo de execução cresce conforme o número de itens cresce, não um valor absoluto em segundos. O(n) significa percorrer a lista uma vez; O(n²) significa, na prática, um loop dentro de outro loop, cada um passando por todos os elementos. Com 100 itens a diferença quase não aparece; com 500 mil, ela domina.
Por que constantes somem na notação Big O
Um ponto contraintuitivo do Selection Sort é que cada passagem verifica menos elementos que a anterior — n, depois n−1, n−2, e assim por diante. A média é n/2, então o tempo seria O(n × n/2). A notação Big O descarta o 1/2 e mantém O(n²).
Constantes são ignoradas porque se tornam irrelevantes na escala em que a análise importa. Compare n = 500 milhões: n² é um número com 17 dígitos, e n²/2 tem quase os mesmos 17 dígitos. Dividir por dois não muda a ordem de grandeza.
Fernanda Kipper é explícita sobre o limite dessa análise: para 100 ou 200 elementos, a escolha do algoritmo quase não muda o resultado. A diferença "começa a gritar" na casa de centenas de milhares ou milhões de itens. Existe exceção: algoritmos recursivos podem estourar a pilha de chamadas com poucas centenas de recursões, antes mesmo de o volume de dados justificar a preocupação.
Como o particionamento do Quick Sort funciona passo a passo
O particionamento separa o array em três partes: elementos menores que o pivô, o próprio pivô, e elementos maiores. Os subarrays resultantes não estão ordenados — estão apenas particionados.
O caso base da recursão é um array com zero ou um elemento, que já está ordenado por definição. Com dois elementos, basta comparar e trocar se necessário. Todo array maior é reduzido até cair nesse caso.
O fluxo completo segue esta ordem:
- Escolha um elemento como pivô.
- Particione o array em menores, pivô e maiores.
- Aplique Quick Sort recursivamente nos dois subarrays.
- Combine subarray esquerdo + pivô + subarray direito.
Segundo a descrição do algoritmo no livro Entendendo Algoritmos, a combinação final é simples: esquerda ordenada + pivô + direita ordenada. Qualquer pivô funciona, desde que o particionamento seja consistente.
O caso base do Quick Sort e a condição de parada recursiva
A condição de parada recursiva do Quick Sort é um array com menos de dois elementos, porque não há nada para ordenar. Toda recursão precisa de um caso base que interrompa a descida, e aqui ele é o menor array possível.
A escolha do pivô define o quanto cada nível da recursão reduz o problema. Com um pivô que divide o array aproximadamente ao meio, você obtém log n níveis. Com um pivô que separa um único elemento por vez, você obtém n níveis — e aí o custo total vira O(n²).
Em 1962, C. A. R. Hoare publicou o Quick Sort no The Computer Journal, vol. 5, nº 1, como parte de um artigo sobre o algoritmo de partição. O pior caso era conhecido desde o início.
Melhor caso, caso médio e pior caso: quando o Quick Sort vira O(n²)
O melhor caso do Quick Sort é O(n log n), o caso médio também é O(n log n), e o pior caso é O(n²). Cada execução do loop de particionamento percorre n elementos; a recursão divide o array em níveis logarítmicos — daí o produto n × log n.
O pior caso aparece quando o pivô divide o array de forma desequilibrada repetidamente. Pior ainda: em arrays já ordenados ou invertidos, escolher sempre o primeiro elemento como pivô produz exatamente esse cenário degenerado, porque cada partição isola um único elemento.
Diferentes escolhas de pivô têm efeitos mensuráveis:
| Estratégia de pivô | Comportamento em array ordenado | Risco de O(n²) |
|---|---|---|
| Primeiro elemento fixo | Degenera em cada partição | Alto |
| Último elemento fixo | Mesmo comportamento do primeiro | Alto |
| Elemento do meio | Divide melhor em arrays já ordenados | Moderado |
| Aleatório | Reduz a chance de pior caso consistente | Baixo na prática |
| Mediana de três | Aproxima um pivô razoável | Baixo na prática |
Bubble Sort vs Quick Sort vs Merge Sort: qual escolher
Bubble Sort, Quick Sort e Merge Sort ocupam faixas de complexidade bem diferentes, e a escolha prática depende de estabilidade, memória disponível e do formato dos dados de entrada.
Comparação direta:
| Algoritmo | Caso médio | Pior caso | Estável | Memória extra |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | Sim | O(1) |
| Selection Sort | O(n²) | O(n²) | Não | O(1) |
| Quick Sort | O(n log n) | O(n²) | Não | O(log n) médio |
| Merge Sort | O(n log n) | O(n log n) | Sim | O(n) |
| TimSort | O(n log n) | O(n log n) | Sim | O(n) |
Bubble Sort usa dois loops aninhados e faz trocas sucessivas. Ele é o exemplo mais didático de O(n²), mas raramente justifica uso em produção. Merge Sort garante O(n log n) mesmo no pior caso, ao custo de memória extra O(n). Quick Sort é rápido e econômico em memória, mas o pior caso existe e precisa ser gerenciado.
Como mitigar o pior caso do Quick Sort na prática
A mitigação mais eficaz do pior caso do Quick Sort é a escolha do pivô. Randomizar ou usar mediana de três reduz drasticamente a chance de divisões degeneradas consistentes, sem alterar o custo do particionamento.
Quando o array for pequeno o suficiente, trocar para Insertion Sort é mais rápido que continuar a recursão — é exatamente o que TimSort faz como parte de sua estratégia híbrida. Essa combinação aparece em bibliotecas de produção há décadas.
Também vale monitorar profundidade de recursão. Se os níveis passarem de 2 × log₂(n), cair para Merge Sort ou Heap Sort garante o limite de O(n log n) mesmo em entradas adversariais. Essa é a estratégia conhecida como introsort, descrita por M. D. McIlroy em artigo apresentado no UNIX Symposium de 1993 em Cambridge, Massachusetts.
Para saber mais sobre estruturas de dados e algoritmos aplicados, o portal CrazyStack reúne trilhas e discussões técnicas da comunidade.
FAQ
- Quick Sort é sempre O(n log n)? Não. O caso médio é O(n log n), mas o pior caso é O(n²) e ocorre quando o pivô divide o array de forma desequilibrada repetidamente. Com pivô aleatório ou mediana de três, a chance de pior caso consistente cai muito na prática.
- Por que o Java usa a estratégia Dual-Pivot Quicksort em vez do Quick Sort clássico? A variante com dois pivôs, adotada em versões recentes do Java, particiona o array em três regiões em vez de duas e reduz o número de operações por passagem. O ganho é atribuído ao design específico da implementação, não a uma propriedade universal da família de algoritmos Quick Sort.
- Qual é a diferença entre divide and conquer e recursão simples? Divisão e conquista significa quebrar o problema em subproblemas menores e resolver cada um recursivamente antes de combinar os resultados. Recursão sozinha apenas repete a função; sem um caso base e sem redução de tamanho, ela não converge.
- Como escolher o pivô do Quick Sort na prática? A escolha mais comum em bibliotecas de produção é mediana de três (primeiro, meio, último) ou aleatório. A estratégia de escolher sempre o primeiro elemento é a que mais degenera em arrays já ordenados.
- Quando devo usar o .sort() da linguagem em vez de implementar Quick Sort? Na maioria dos casos, sempre use o nativo. Ele já incorpora heurísticas testadas em produção, evita pior caso e é otimizado em C ou Rust por baixo. Implemente Quick Sort manualmente apenas quando precisar de um comparador específico, controlar o uso de memória ou entender o comportamento do motor de execução.
Da live ao texto: transforme suas explicações em artigo
Explicar Quick Sort ao vivo funciona porque você mostra dedos, desenha subarrays e improvisa exemplos. Só que esse mesmo raciocínio — Selection Sort explicado com contadores de plays, o custo de constantes em Big O, o pior caso do pivô fixo — costuma ficar preso no vídeo e nunca chega a quem procura por "quick sort" em um buscador. O conhecimento existe; falta o texto.
É exatamente isso que o canal Dev Doido do canal do youtube faz de outro jeito no formato vídeo, e é o que muita gente com conteúdo técnico bom ainda não conseguiu fazer no formato escrito. Se você tem lives, entrevistas ou aulas com conteúdo denso sobre algoritmos e estruturas de dados, dá para reaproveitar esse material em texto.
No Skala Blog, você cola a URL do vídeo, a ferramenta transcreve o áudio e gera uma versão escrita pronta para revisão. O texto sai na sua voz, com os exemplos que você já explicou, e você decide o que publicar.