Uma posição deixa de ser provisória.
Nesta implementação de Lomuto, ao fim da partição, os itens à esquerda da fronteira são menores que o pivô; os itens à direita são maiores ou iguais. O pivô fica entre essas regiões e sai das próximas chamadas.
02 / sorting
Quick Sort.
Escolha um pivô, separe menores e maiores e resolva as partes.
/ visualização passo a passo
Separa menores e maiores ao redor de um pivô.
palco / Quickmotivo / Quick
000 comparações000 trocas0% progresso pronto
telemetria / passo ao vivo
passo atual00input carregado — pronto para executar
etapa de código01destaque sincronizado por linguagem
entrada16elementos em memória
estadoreadycontrole manual
playback observado · ordenação
Duração que aconteceu.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
média / últimas 0—Quick · armazenamento local
sem registros ainda
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
/ leitura em três sinais
O que a bancada revela?
Separa menores e maiores ao redor de um pivô. Cada barra representa um item; a cor quente marca a comparação atual e o verde calmo indica que uma posição já não precisa ser revisitada.
quando usarUse quando você quer bom desempenho médio em sequências na memória e não precisa preservar a ordem original de valores iguais.
complexidade
melhor casoO(n log n)
caso médioO(n log n)
pior casoO(n²)
Frequentemente rápido na prática; a escolha do pivô muda o comportamento.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o número de operações tende a crescer quando n, a quantidade de itens, aumenta.
operações
O(n²) · Crescimento quadrático
Há comparações entre pares de itens ou varreduras repetidas. Por isso, cada aumento de entrada multiplica mais rapidamente o trabalho necessário.
Se a entrada dobra, o número de comparações pode ficar perto de quatro vezes maior.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para observar por que O(n²) acumula trabalho mais depressa que O(n log n) quando a lista cresce. Merge Sort tende a crescer mais devagar do que Bubble Sort quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
O pivô não ordena tudo.
Ele traça uma fronteira.
Na bancada, o último item do segmento vira o pivô. A varredura não tenta resolver a lista inteira: ela separa valores menores à esquerda e os demais à direita. Depois da troca final, o pivô ocupa uma posição que já não será revisitada.
boundary é a fronteira visível.
Durante a varredura, tudo antes de boundary já atende à regra “menor que o pivô”. Cada item que passa no teste é trocado para essa região; os demais permanecem à direita, à espera da troca final.
Resolver menos é o que garante o término.
As chamadas seguintes recebem segmentos estritamente menores, à esquerda e à direita da posição final do pivô. Zero ou um item já está ordenado, formando o caso-base da recursão.
/ custo e robustez
O balanço das partições decide a curva.
Cada particionamento percorre o segmento uma vez. Quando os pivôs dividem os dados de forma razoavelmente equilibrada, o custo esperado é Θ(n log n). Se pivôs extremos se repetem, sobra um subproblema de tamanho quase n − 1 e o pior caso chega a Θ(n²).
PARTIÇÃO DA BANCADALomutoPivot no último item, para leitura direta.
CASO ESPERADOΘ(n log n)Com posições de pivot aleatórias.
PIOR CASOΘ(n²)Partições extremas repetidas.
ESTABILIDADENÃOTrocas distantes podem inverter iguais.
DECISÃO DE ENGENHARIA
Um pivot aleatório reduz previsibilidade; não cria uma garantia.
Em uma versão mais robusta, pode-se embaralhar a entrada ou sortear o pivot, usar partição em três vias quando há muitas duplicatas, recorrer primeiro sobre o menor lado para limitar a pilha e trocar de estratégia quando a profundidade cresce demais. Essas técnicas atacam riscos distintos. Para estabilidade ou garantia de Θ(n log n), compare com Merge Sort; para biblioteca de produção, algoritmos híbridos como Introsort merecem consideração.
/ por baixo do palcoPseudocódigo e
destaque sincronizado por linguagemPseudocódigo e
implementação.
etapa / 00
input carregado — pronto para executar
O destaque acompanha o mesmo passo que você vê nas barras. Execute em câmera lenta para conectar intenção e efeito.
linha atual comentário de estado
function quickSort(items, low = 0, high = items.length - 1) { // Partition values around the last pivot if (low >= high) return items; const pivot = items[high]; let boundary = low; for (let i = low; i < high; i++) { if (items[i] < pivot) { [items[i], items[boundary]] = [items[boundary], items[i]]; boundary++; } } [items[boundary], items[high]] = [items[high], items[boundary]]; quickSort(items, low, boundary - 1); quickSort(items, boundary + 1, high); return items;}/ mesma entrada · duas leiturasComparação
Comparação
lado a lado.
A / Quick pronto
0comparações0 trocas
B / Bubble pronto
0comparações0 trocas
03 prática
/ decisão de engenhariaOnde esta estratégia
Onde esta estratégia
encaixa?
Use quando você quer bom desempenho médio em sequências na memória e não precisa preservar a ordem original de valores iguais. A melhor forma de internalizar essa escolha é comparar o mesmo cenário com outras estratégias e observar como as métricas se comportam.
testar no modo corrida