If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Insertion sort

Existem muitos modos diferentes de ordenar. Conforme a ordenação por seleção é executada, o subarray no começo do array é ordenado, mas o subarray no final não. A ordenação por seleção (selection sort) escaneia o subarray não ordenado em busca do próximo elemento a ser incluído nele.
Aqui está outro modo de pensar sobre ordenação. Imagine que você está jogando cartas. Você está com as cartas na mão, e elas estão ordenadas. Você recebe exatamente uma nova carta. Você deve colocá-la na posição correta, de forma que as cartas na sua mão continuem ordenadas. Na ordenação por seleção, cada elemento que você adiciona ao subarray ordenado não é menor que os elementos que já estão no subarray ordenado. Mas no nosso exemplo de cartas, a nova carta pode ser menor que algumas das cartas que você já está segurando, e então você as examina, comparando a nova carta com todas as cartas na sua mão, até encontrar a posição para colocá-la. Você insere a nova carta na posição correta, e, novamente, sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até você não receber mais cartas.
Esta é a ideia por trás da ordenação por inserção. Percorra as posições do array, começando com o índice 1. Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no subarray ordenado à esquerda daquela posição. Aqui está uma visualização que mostra isso:
Em termos de arrays, imagine que o subarray do índice 0 até o índice 5 já está ordenado, e queremos inserir o elemento atualmente no índice 6 neste subarray ordenado, de forma que o subarray do índice 0 até o índice 6 fique ordenado. É assim que começamos:
Inserção
E é assim que o subarray deve se parecer quando tivermos terminado:
Inserção
Para inserir o elemento da posição 6 no subarray à sua esquerda, o comparamos repetidamente com os elementos à sua esquerda, indo da direita para a esquerda. Vamos chamar o elemento na posição 6 de chave. Sempre que descobrimos que a chave é menor que um elemento à sua esquerda, deslocamos esse elemento uma posição para a direita, já que sabemos que a chave deverá ficar à esquerda desse elemento. Vamos precisar de duas coisas para fazer essa ideia funcionar: precisamos ter uma operação de deslocamento que mova um elemento uma posição à direita, e precisamos salvar o valor da chave em uma posição separada (de modo que ela não seja sobrescrita pelo elemento imediatamente à sua esquerda). Em nosso exemplo, vamos colocar o elemento no índice 6 em uma variável chamada key:
Inserção
Agora, comparamos key com o elemento na posição 5. Descobrimos que key (5) é menor que o elemento na posição 5 (13), então deslocamos esse elemento para a posição 6:
Inserção
Note que a operação deslocamento simplesmente copia o elemento uma posição para a direita. Agora, comparamos key com o elemento na posição 4. Descobrimos que key (5) é menor que o elemento na posição 4 (10), e deslocamos esse elemento:
Inserção
Depois, comparamos key com o elemento na posição 3 e deslocamos esse elemento:
Inserção
O mesmo acontece com o elemento na posição 2:
Inserção
Agora, chegamos ao elemento na posição 1, que tem um valor de 3. Este elemento é menor do que key, então não precisamos deslocá-lo. Em vez disso, colocamos key na posição imediatamente à direita desse elemento (ou seja, na posição 2), cujo elemento foi mais recentemente deslocado para a direita. O resultado é que o subarray do índice 0 até o índice 6 foi ordenado:
Inserção
A ordenação por inserção insere um elemento no subarray ordenado à sua esquerda. Inicialmente, podemos dizer que o subarray que contém apenas o índice 0 está ordenado, já que ele contém apenas um elemento, e como pode um único elemento não estar ordenado em relação a si mesmo? Ele deve estar ordenado. Vamos trabalhar em um exemplo. Aqui está nosso array inicial:
Insertion sort
Como o subarray que contém apenas o índice 0 é nosso subarray ordenado inicial, a primeira chave está no índice 1. (Vamos mostrar o subarray ordenado em vermelho, a chave em amarelo, e a parte do array com que ainda temos que lidar em azul). Inserimos a chave no subarray ordenado à sua esquerda:
Insertion sort
Agora, o subarray ordenado vai do índice 0 até o índice 1, e a nova chave está no índice 2. O inserimos então no subarray ordenado à sua esquerda:
Insertion sort
Continuamos com esse processo, considerando cada elemento do array, um por vez, como a chave e o inserimos no subarray ordenado à sua esquerda:
Insertion sort
Insertion sort
Insertion sort
Depois que inserimos o elemento mais à direita no array, teremos ordenado todo o array:
Insertion sort
Algumas situações que surgem em nosso exemplo merecem ser estudadas um pouco mais: quando a chave sendo inserida for menor do que todos os elementos à sua esquerda (como quando inserimos as chaves 2 e 3), e quando é maior ou igual a todos os elementos à sua esquerda (como quando inserimos a chave 13). No primeiro caso, todos os elementos no subarray à esquerda da chave se deslocam uma posição para a direita, e devemos parar quando chegarmos à extremidade esquerda do array. No último caso, na primeira vez que comparamos a chave com um elemento à sua esquerda, descobrimos que a chave já está na sua posição correta em relação a todos os elementos à sua esquerda. Nenhum elemento é deslocado e a chave retorna à posição em que começou.

Inserir um valor em um subarray ordenado

A parte principal da ordenação por inserção é abrir espaço em um array para colocar o valor atual, que é armazenado na variável key. Como vimos antes, percorremos o subarray à esquerda da posição inicial de key, da direita para a esquerda, deslocando cada elemento que seja maior do que key uma posição para a direita. Quando encontramos um elemento que seja menor do que key, ou igual a key, paramos de deslocar e copiamos key para a posição vaga imediatamente à direita deste elemento. (É claro, a posição não está realmente vazia, seu elemento foi deslocado para a direita). Este diagrama mostra a ideia:
Inserção

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

  • Avatar piceratops ultimate style do usuário Daniel De Santana Sforzim
    Fui completamente incapaz de concluir o desafio: implementar o insert, o texto acima não me ajudou a concluir o exercício. me parece muito superficial a explicação.
    (6 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar winston baby style do usuário Willian Arana
    Se alguém estiver com dificuldade no desafio a seguir, segue uma solução:

    var insert = function(array, rightIndex, value) {
    var currentIndex;
    for(currentIndex = rightIndex; currentIndex >= 0 && array[currentIndex] > value; currentIndex--) {
    array[currentIndex + 1] = array[currentIndex];
    }
    array[currentIndex + 1] = value;
    };
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
  • Avatar leaf green style do usuário Guilherme Albuquerque
    Depois do laço for, aparece assim: "array[i + 1] = value;", sendo que eu leio isso da seguinte forma: "O valor do índice à direita de 'i' recebe o valor de 'value'", mas eu não entendo ainda se value é o mínimo, (que é menor que o valor de key) ou se ele é a própria 'key'. Agradeço desde já às respostas...
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
    • Avatar leafers seed style do usuário cesar
      Ao fazer array [i+1] = value vc está deslocando os elementos para a direita .
      Vc somente irá desclocar esse elemento pra direita, se Array[i] > array[ key].
      Caso contrário, quando array[i] < array [key], temos que colocar a chave no lugar em seguida da posicao i, ou seja
      array[i +1 ]= array [key], pois dess
      (1 voto)
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.