- A inserir
- Comparados
- Trocados
- Parte ordenada
Ordenação por inserção
A ordenação por inserção funciona como muitas pessoas ordenam as cartas que têm na mão. Mantém uma parte ordenada no início da lista, pega no valor seguinte e fá-lo recuar para lá de cada valor maior até encaixar. Reproduza a ordenação a qualquer velocidade, ou avance uma comparação de cada vez, e acompanhe os contadores de comparações, trocas e passagens. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Os contadores mostram comparações, trocas e passagens. Escolha quantas barras, como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
- Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
- Experimente uma lista quase ordenada e uma invertida, e compare de quantas comparações cada uma precisa.
Como funciona a ordenação por inserção
O primeiro valor sozinho é uma parte ordenada. Pegue no segundo valor e compare-o com o anterior; se o anterior for maior, troque-os, e continue a comparar e a trocar até o anterior não ser maior ou o valor chegar ao início. Agora os dois primeiros valores estão por ordem. Faça o mesmo com o terceiro valor, o quarto, e assim por diante até ao fim da lista.
Rápida em listas quase ordenadas
Cada passagem para no primeiro valor que não é maior, por isso um valor que já está perto do seu lugar custa só uma ou duas comparações. Uma lista ordenada precisa de n − 1 comparações e nenhuma troca; uma lista invertida, o pior caso, precisa de n(n − 1)/2 de cada. O número de trocas é sempre igual ao número de inversões da lista inicial, os pares fora de ordem. É por isso que a ordenação por inserção é muito usada em listas curtas ou quase ordenadas, e dentro de ordenações mais rápidas para terminar pedaços pequenos.
Perguntas frequentes
Como funciona a ordenação por inserção?
Constrói uma parte ordenada no início da lista. Cada passagem pega no valor seguinte e fá-lo recuar para lá de cada valor maior que o antecede, até encaixar. Após a passagem k, os primeiros k + 1 valores estão por ordem, embora um valor posterior ainda possa ser inserido entre eles.
Quantas comparações e trocas faz a ordenação por inserção?
O número de trocas é sempre igual ao número de inversões da lista inicial: nenhuma numa lista ordenada, n(n − 1)/2 numa invertida. As comparações são as trocas mais, no máximo, uma por passagem, ou seja, entre n − 1 e n(n − 1)/2.
Porque é que a ordenação por inserção é rápida em listas quase ordenadas?
Porque uma passagem para assim que encontra um valor que não é maior. Quando cada valor está perto do seu lugar final, cada passagem é curta, e a ordenação toda demora um tempo próximo de n.
A ordenação por inserção é estável?
Sim. Um valor só passa por valores estritamente maiores, por isso valores iguais nunca se ultrapassam e mantêm a sua ordem original.
Os meus números são enviados para algum lado?
Não. A ordenação corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor