Prefixo pronto
Antes da iteração i, o trecho à esquerda contém exatamente os itens já lidos, em ordem não decrescente. O restante ainda não precisa obedecer a nenhuma ordem.
04 / sorting
Insertion Sort.
Construa uma região ordenada, inserindo cada item no lugar certo.
/ visualização passo a passo
Amplia a zona ordenada um item por vez.
palco / Insertionmotivo / Insertion
000 comparações000 deslocamentos0% 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—Insertion · 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?
Amplia a zona ordenada um item por vez. 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 os dados já chegam quase ordenados ou quando você precisa de uma implementação pequena e estável.
complexidade
melhor casoO(n)
caso médioO(n²)
pior casoO(n²)
Ótimo para listas pequenas ou quase ordenadas.
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.
/ análise técnica · prefixo, inversões e adaptatividadeOrdenar é manter
Ordenar é manter
o próximo item no lugar.
O Insertion Sort cresce um prefixo já ordenado. Em cada passo, ele retira a chave atual, abre uma lacuna deslocando apenas os elementos maiores e insere a chave na primeira posição compatível. Essa leitura local explica por que o algoritmo responde tão bem quando a entrada já está quase organizada.
Abra a lacuna
Ao deslocar somente valores maiores que a chave, nenhuma ordem válida do prefixo é perdida. Ao inserir a chave na lacuna, o prefixo cresce de tamanho e continua ordenado.
Todo o vetor
O índice avança uma posição por iteração. Quando alcança o fim, o prefixo coincide com o vetor completo; portanto, a sequência inteira está ordenada.
/ propriedades operacionaisPor que a entrada
Por que a entrada
faz tanta diferença?
O algoritmo é adaptativo: não executa o mesmo volume de deslocamentos em todos os vetores de mesmo tamanho. Para um vetor ordenado, cada chave só confirma sua posição. Para um vetor invertido, cada nova chave atravessa todo o prefixo anterior.
melhor casoO(n)entrada já ordenada
médio e piorO(n²)muitas inversões
memória extraO(1)ordenação in-place
estabilidadesim*com teste estrito
>ESTÁVEL POR CONSTRUÇÃONão trocar iguais
Não trocar iguais
preserva sua ordem.
Se o loop desloca apenas valores estritamente maiores que a chave, dois itens iguais mantêm a ordem de chegada. Essa garantia é relevante quando a chave de ordenação é apenas um dos campos de um registro.
DECISÃO DE ENGENHARIA
Use em coleções pequenas, fluxos quase ordenados ou como caso-base de algoritmos híbridos. Evite como estratégia principal para grandes coleções sem estrutura: Merge Sort, Heap Sort e Quick Sort robusto têm crescimento mais favorável nesses cenários.
/ 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 insertionSort(items) { // Insert each value into the sorted region for (let i = 1; i < items.length; i++) { const current = items[i]; let j = i - 1; while (j >= 0 && items[j] > current) { items[j + 1] = items[j]; j--; } items[j + 1] = current; } return items;}/ mesma entrada · duas leiturasComparação
Comparação
lado a lado.
A / Insertion pronto
0comparações0 deslocamentos
B / Bubble pronto
0comparações0 trocas
03 prática
/ decisão de engenhariaOnde esta estratégia
Onde esta estratégia
encaixa?
Use quando os dados já chegam quase ordenados ou quando você precisa de uma implementação pequena e estável. 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