Ordenação por inserção
Constrói uma parte ordenada à esquerda, um valor de cada vez. Cada novo valor é retirado e anda para a esquerda até encontrar um valor menor.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- sim
- sim
Melhor caso: como o tempo cresce com o tamanho n da lista quando a entrada é a mais fácil para este algoritmo.
Caso médio: como o tempo costuma crescer com n. Com n², o dobro de valores demora cerca de quatro vezes mais; n log n cresce bem menos.
Pior caso: o crescimento com a entrada mais difícil. Útil quando a velocidade nunca pode cair.
Memória: quanta memória extra é necessária além da lista. 1 significa algumas variáveis; n, uma cópia da lista.
Estável: dois valores iguais mantêm a ordem original. Importa quando se ordena por um só campo de um registo.
Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- a comparar
- a mover
- na mão
- parte ordenada
- na posição final
Pares fora de ordem: 154 (no início: 154) fora de ordem posto em ordem Os dois eixos: valores do menor para o maior
Carregue em Reproduzir: as linhas mostram como o custo cresce
Carregue em Reproduzir ou avance passo a passo pelo algoritmo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
Experimente: Escolha uma lista quase ordenada. Quase nada se desloca, por isso termina em muito poucos passos.
Como funciona
A parte da esquerda está sempre ordenada. Retira-se o valor seguinte, cada valor maior da parte ordenada desloca-se uma posição para a direita e o valor entra no espaço vazio. É assim que muita gente ordena as cartas que tem na mão.
Quando é uma boa escolha
Boa escolha para listas curtas e para listas quase ordenadas, onde é muito rápido. As bibliotecas de ordenação reais usam-no nos pedaços pequenos da lista, dentro de métodos mais rápidos.