Algoritmos de Ordenação: Insertion Sort

Dando sequência à série, agora será explicado outro algoritmo de ordenação conhecido como insertion sort (ordenação por inserção).

Vamos ao Insertion Sort

A ideia do insertion sort consiste em ordenar os itens, inserindo-os na posição corresponde da lista. Mas, o que isso quer dizer afinal?

Vamos utilizar um exemplo do mundo real para melhor compreensão da ideia por trás do algoritmo: um baralho francês.

Imagine que você esteja comprando uma carta e que você já tenha algumas cartas na sua mão, as quais você já fez o trabalho de ordenar corretamente.

Você não sabe que carta virá, mas por motivos de organização para o jogo, gostaria de manter a ordenação conforme as cartas vão para sua mão.

No momento em que você saca uma carta, o valor se torna a referência para você fazer a ordenação (chamaremos de “chave” daqui para a frente) e então, começa a comparar o valor com as cartas da sua mão (começando da última carta à direita) em direção à esquerda, até que encontre uma carta que seja maior ou igual à esta.

Finalmente, você descobre que posição esta carta deve ficar de acordo com a ordem das cartas. Porém, as outras cartas que já estão na sua mão e são maiores precisam ser movidas para a direita para essa carta ser “encaixada” ou inserida naquela posição.

Essa é exatamente a ideia por trás do insertion sort.

Então, em resumo:

• Compare o valor do item “chave” que está entrando com os outros itens até que se sua posição seja encontrada. Essa comparação é feita em direção à esquerda.
• Se o item que você está comparando for menor, desloque o item para a direita , visando “abrir” um novo espaço para colocar a carta na posição correspondente);
• Finalmente ao encontrar um item maior ou não haver mais itens, significa que você encontrou a posição que este item deve estar: coloque o item “chave” na posição correspondente.

Vamos à um exemplo do algoritmo em execução (como sempre fazemos durante esta série :)).

Vamos voltar atrás e lembrar do selection sort. No post anterior, dividimos a lista entre lista ordenada e a lista não ordenada. Faremos a mesma coisa no insertion sort.

A chave(3) está na posição 1 (segunda posição) da lista, pois não há ninguém à se comparar se pegassemos o prmeiro item da lista. Então consideramos que o primeiro elemento da lista (5) já esteja ordenado.

Precisamos comparar com os itens à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do primeiro elemento à sua esquerda (valor 5). A chave (valor 3) é menor, maior ou igual ao elemento comparado (valor 5)? Menor! Então temos que movimentar o elemento (valor 5) para a direita.

Como a chave é menor que o elemento comparado, “abrimos” um espaço para inserí-la em seu respectivo lugar correspondente à ordenação. O “abrir um espaço” significa mover o item comparado(valor 5) com a chave (valor 3) à direita da lista (ou para a posição que estava + 1).

Como chegamos ao início da lista e não há mais itens a comparar, podemos colocar a chave (3) na posição correspondente. Assim, nossa lista ordenada agora possuem dois itens: 3 e 5

O item que queremos inserir (chave) está agora na posição 2.

Precisamos comparar com os itens à sua esquerda (ou os itens já previamente ordenados) da chave. Ela é comparada ao valor do primeiro elemento à sua esquerda (5). A chave (1) é menor ou igual ao elemento comparado (5)? Menor! Então temos que movimentar o elemento (5) para a direita.

Precisamos comparar com o próximo item à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do segundo elemento à sua esquerda na posição 0 (valor 3). A chave (valor 1) é menor ou igual ao elemento comparado (3)? Menor! Então temos que movimentar o elemento da posição 0 (valor 3) para a direita.

Precisamos comparar com o próximo item à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do segundo elemento à sua esquerda na posição 0 (valor 3). A chave (valor 1) é menor ou igual ao elemento comparado (3)? Menor! Então temos que movimentar o elemento da posição 0 (valor 3) para a direita.

Como a chave é menor que o elemento comparado, “abrimos” um espaço para inserí-la em seu respectivo lugar correspondente à ordenação. O “abrir um espaço” significa mover o item comparado(valor 3) com a chave (1) à direita da lista (ou para a posição que estava + 1).

Como chegamos ao início da lista e não há mais itens a comparar, podemos colocar a chave (valor 1) na posição correspondente (ao qual por meio das comparações, descobrimos que é a posição 0). Assim, nossa lista ordenada agora possui três itens: 1, 3 e 5

A chave agora está na posição 3 da lista (valor 2).

Precisamos comparar com os itens à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do primeiro elemento à sua esquerda (valor 5). A chave (valor 2) é menor ou igual ao elemento comparado (valor 5)? Menor! Então temos que movimentar o elemento (5) para a direita.

Como a chave é menor que o elemento comparado, “abrimos” um espaço para inserí-la em seu respectivo lugar correspondente à ordenação. O “abrir um espaço” significa mover o item comparado (valor 5) com a chave (valor 2) à direita da lista (ou para a posição que estava + 1).

Precisamos comparar com o próximo item à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do segundo elemento à sua esquerda na posição 1 (valor 3). A chave (valor 2) é menor, maior ou igual ao elemento comparado (3)? Menor! Então temos que movimentar o elemento da posição 1 (valor 3) para a direita.

Como a chave é menor que o elemento comparado, “abrimos” um espaço para inserí-la em seu respectivo lugar correspondente à ordenação (ainda não sabemos o lugar exato, mas sabemos que temos que continuar percorrendo para encontrar). O “abrir um espaço” significa mover o item comparado (valor 3) com a chave (valor 2) à direita da lista (ou para a posição que estava + 1).

Precisamos comparar com o próximo item à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do tercero elemento à sua esquerda na posição 0 (valor 1). A chave (valor 2) é menor, maior ou igual ao elemento comparado (1)? Maior! Isso significa que descobrimos que a chave deve ficar uma posição após (à direita) deste item e não precisamos mais percorrer a lista à esquerda, pois todo resto também será menor que a chave. Então temos que inserir o valor da chave (valor 2) em seu lugar correspondente (posição 1)

Como descobrimos um item que é maior que a chave (valor 2) , podemos colocá-la na posição correspondente (ao qual por meio das comparações, descobrimos que é a posição 0). Assim, nossa lista ordenada agora possui quatro itens: 1, 2, 3 e 5.

A chave(valor 4) está na posição 4 (quinta posição) da lista

Precisamos comparar com os itens à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do primeiro elemento à sua esquerda (valor 5). A chave (valor 4) é menor, maior ou igual ao elemento comparado (valor 5)? Menor! Então temos que movimentar o elemento (valor 5) para a direita.

Como a chave é menor que o elemento comparado, “abrimos” um espaço para inserí-la em seu respectivo lugar correspondente à ordenação. O “abrir um espaço” significa mover o item comparado (valor 5) com a chave (valor 4) à direita da lista (ou para a posição que estava + 1).

Precisamos continuar comparar com os itens à esquerda (itens já ordenados) da chave. Ela é comparada ao valor do segundo elemento à sua esquerda (valor 3). A chave (valor 4) é menor, maior ou igual ao elemento comparado (valor 3)? Maior! Isso significa que descobrimos que a chave deve ficar uma posição após este elemento (à direita) e não precisamos mais percorrer os outros itens que estão à esquerda: lembre-se que tudo que está à esquerda já está ordenado, que nos diz que todos os outros elementos serão menores que a chave. Assim, podemos inserir o valor da chave em seu lugar correspondente (posição 3)

Finalmente, todos os elementos estão ordenados.

Desempenho

Apesar de essencialmente ser parecido com o selection sort, há algumas diferenças que valem a pena citar.

No selection sort, não temos pior e melhor caso. Ele sempre executará a mesma quantidade de vezes dado o tamanho da lista, não importa que itens venham na entrada.

Outra diferença se comparado ao selection sort é que há mais movimentações na lista (ocorrendo inplace). Caso o cenário dado haja alguma limitação ou maior custo para movimentação (I/O), selection sort seria uma melhor opção.

Já o insertion sort realiza menos operações se comparado ao selection sort caso a lista esteja quase ordenada.

Por exemplo, no melhor caso para o insertion sort é uma lista já ordenada, pois precisaria percorrer n — 1 vezes (todos os elementos da lista, com exceção ao primeiro).

Em relação às desvantagens, o insertion sort é um algoritmo com uma performance ruim para grande quantidades de itens a serem ordenados, pois assim como selection e bubble sort, ele precisa percorrer a lista para cada elemento (n * n = O(n²) — será explicado a seguir o porquê do algoritmo ser O(n²)).

Vamos utilizar o pior caso para realizar a análise assintótica: uma lista em ordem decrescente com os elementos: 5, 4, 3, 2, 1

Ao realizar o insertion sort, lembre-se que começamos pelo segundo item da lista. Este item será comparado com o elemento da primeira posição (1 operação)

Ao realizar o processo para o próximo item (valor 3), serão comparado dois itens que já foram ordenados: 4 e 5 (lembre-se, a comparação é feita até que se encontre alguém maior que à esquerda da posição da chave ou chegue ao fim da lista. Estamos analisando um pior caso que sempre percorrerá toda a lista nas comparações e sabemos que 3 não é maior que 4 e 5) (2 operações)

Ao realizar o processo para o próximo item (valor 2), serão comparado três itens que já foram ordenados: 3, 4 e 5 (lembre-se, a comparação é feita até que se encontre alguém maior que à esquerda da posição da chave ou chegue ao fim da lista. Estamos analisando um pior caso e sabemos que 2 não é maior que 3, 4, 5) (3 operações)

Ao realizar o processo para o último item (valor 1), serão comparado quatro itens que já foram ordenados: 2, 3, 4 e 5 (lembre-se, a comparação é feita até que se encontre alguém maior que à esquerda da posição da chave ou chegue ao fim da lista. Estamos analisando um pior caso e sabemos que 1 não é maior que 2, 3, 4, 5) (4 operações).

Vamos então verificar quantas operações foram necessárias:

4 + 3 + 2 + 1 = 10 operações

Caso fosse uma lista decrescente com os elementos 6, 5, 4, 3, 2, 1 teríamos:

5 + 4 + 3 + 2 + 1 = 15 operações

Se você leu o post sobre selection sort, isso soa familiar? É isso mesmo! O pior caso para insertion sort é o mesmo número de operações que o selection sort sempre leva para qualquer caso. Caso não tenha lido ou não lembre, vamos fazer um resumo:

Podemos agrupar essas somas em pares dos maiores com os menores valores respectivamente, pois a adição de cada par sempre será o número de elementos da lista (Por exemplo, numa lista decrescente com cinco elementos são necessárias dez operações para ordená-la ou: 1 + 2 + 3 + 4 + 5. Se agruparmos em pares os menores e os maiores, a soma dos mesmos sempre será cinco)

1 + 2 + 3 + 4 = (4 + 1) + (3 + 2)
(4 + 1) = 5
(3 + 2) = 5

Para descobrir o número de pares dado o número de elementos (n) em uma lista:

(n — 1) / 2

Sabemos também que a soma de cada par é o mesmo que o tamanho da lista. Logo, podemos multiplicar a soma de cada par (n) pela quantidade pares:

tamanho da lista * número de pares 
n * (n — 1) / 2
(n² - n) / 2
(n² / 2) - (n / 2) = O(n²)

Assim como selection sort, sua análise assintótica é O(n²).

Existem casos que seu uso é adequado. Por exemplo, caso seja inseridos novos elementos na lista muitas vezes e essa lista já esteja ordenada, é necessário percorrer toda a lista apenas uma vez para descobrir a posição em que aquele item deve ficar. Em outras palavras: não é necessário executar todo o processo de ponta a ponta como em outros algoritmos de ordenação.

Exemplo

Por fim, um exemplo de código do algoritmo utilizando Python:

E por agora é só :)