Comparações
Trocas
Passagem

  • A inserir
  • Comparados
  • Trocados
  • Parte ordenada

Mais sobre a ordenação por inserção

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

  1. 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.
  2. 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.
  3. 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