Algoritmo de ordenação Insertion Sort

Trecho de código do algoritmo Insertion Sort

Os algoritmos de ordenação para arrays são um dos mais estudados por quem está sendo introduzido no universo dos algoritmos e estruturas de dados. Além de possuírem diversos tipos de implementação, esses algoritmos são extremamente úteis e aplicáveis em cenários reais dos projetos de software, fato que desperta o interesse da maioria dos desenvolvedores.

Da mesma maneira que os algoritmos de busca e outras famílias de algoritmos, os algoritmos de ordenação apresentam tanto algoritmos de baixa complexidade, quanto de alta complexidade de tempo. O consumo do espaço auxiliar de memória e a diferença na curva de aprendizagem também se notabilizam como fatores que variam bastante entre cada algoritmo de ordenação.

O algoritmo Insertion Sort, junto dos seus pares Bubble Sort e Selection Sort, desponta na lista dos algoritmos de ordenação com menor nível de eficiência sob a óptica do tempo de execução. Por outro lado, o entendimento da sua lógica e a construção do seu código-fonte exigem pouquíssimo esforço.

No decorrer desta publicação, todos os detalhes em torno do algoritmo Insertion Sort serão devidamente explicados, de tal forma que seja possível classificar a sua performance e assimilar o seu funcionamento. 

Entendendo o algoritmo

A estratégia de ordenação do Insertion Sort trabalha com a ideia de dividir virtualmente o vetor em duas partes, uma ordenada e a outra não ordenada. Os números do segmento não ordenado são selecionados e colocados na posição correta da fração ordenada. Fazendo uma correlação, o algoritmo se comporta como alguém que precisa ordenar as cartas de um baralho.

Execução do algoritmo Insertion Sort

Considere o array hipotético arr, composto pelos elementos [6, 5, 3, 1, 8, 7, 2, 4] presentes na imagem animada logo acima. Inicialmente, o Insertion Sort compara os dois primeiros itens do vetor. Neste caso, o número seis supera o número cinco. Desse modo, os elementos são trocados de posição, e o número cinco passa a integrar o subarray dos itens ordenados.

Dando sequência para o seu processamento, o Insertion Sort compara os próximos dois elementos. O número seis obviamente leva vantagem em detrimento do número três, e com isto ambos tem as suas posições alternadas. Entretanto, o número três é menor do que o número cinco. Desse jeito, mais uma vez o número três muda de posição. Agora, os números três e cinco incorporam o subarray ordenado.

Retomando do último passo, novamente o Insertion Sort realiza a comparação dos elementos seguintes do vetor. O número um é inferior em relação ao número seis, bem como aos números cinco e três. Ou seja, o número um deixa de ocupar o terceiro índice de arr, chegando até a posição zero do array. Portanto, o número um entra para o grupo dos itens ordenados.

O processo continua em repetição até que o array arr seja completamente percorrido e ordenado. Sem dúvida alguma, a compreensão do racional que abrange o Insertion Sort requer muito menos afinco do que algoritmos da linhagem do Merge Sort, por exemplo.

Analisando a implementação do algoritmo

Eficiente para conjuntos pequenos de dados que estejam parcialmente ordenados, o Insertion Sort ostenta uma complexidade quadrática de tempo. Isso significa que do ponto de vista da notação Big O, o desempenho do algoritmo está no mesmo patamar do Bubble Sort.

Em termos gerais, o passo a passo da implementação do Insertion Sort está descrito a seguir.

1. As variáveis i, j e chave são declaradas no início da função. A variável i controla os elementos da parte ordenada do vetor arr, enquanto j controla os itens da parte não ordenada. Por sua vez, chave armazena o número usado como referência na ordenação da estrutura.
2. O loop for varre o array arr em sua totalidade, com o intuito que todos os elementos sejam verificados e colocados na sua posição adequada.
3. A variável chave recebe o elemento da iteração atual de i. Esse número será comparado com os seus antecessores no vetor arr, a fim de reposicioná-lo no índice correto.
4. A variável j recebe o índice anterior à i, ou seja, aponta para o número que precede chave no vetor arr.
5. O loop while inicia a ordenação dos elementos de arr. Para isso, o laço de repetição checa se o índice j não excede os limites do array (j >= 0), e se o elemento no próprio índice j está fora de ordem (arr[j] > chave). Até que essas duas condições deixem de ser verdadeiras, cada item no índice j é movido para a posição seguinte do vetor (j + 1). 
6. Quando o loop while garante que os números desordenados foram rearranjados, o elemento chave é inserido no índice vago (j + 1).

Comparando o desempenho do algoritmo com o Bubble Sort

Dado que o Bubble Sort é o algoritmo de ordenação mais básico que os programadores têm a sua disposição, tanto no que tange à implementação, quanto no que diz respeito à performance, costuma ser um procedimento padrão usá-lo como um comparativo no momento de analisar outros algoritmos.

Embora o Insertion Sort e o Bubble Sort possuam uma complexidade de tempo quadrática, o algoritmo Insertion Sort demonstra ser uma escolha mais veloz em boa parte dos casos, conforme está evidenciado no quadro abaixo. Ademais, observando o uso do espaço auxiliar de memória, o Insertion Sort mantém uma complexidade constante, em linha com o Bubble Sort.

Método	Input	Média de tempo	Espaço alocado
MétodoInsertionSort	InputInt32[10]	Média de tempo9.384 ns	Espaço alocado-
MétodoBubbleSort	InputInt32[10]	Média de tempo40.923 ns	Espaço alocado-
MétodoInsertionSort	InputInt32[100]	Média de tempo104.724 ns	Espaço alocado-
MétodoBubbleSort	InputInt32[100]	Média de tempo3,896.600 ns	Espaço alocado-
MétodoInsertionSort	InputInt32[1000]	Média de tempo986.409 ns	Espaço alocado-
MétodoBubbleSort	InputInt32[1000]	Média de tempo372,929.548 ns	Espaço alocado-
MétodoInsertionSort	InputInt32[10000]	Média de tempo9,964.832 ns	Espaço alocado-
MétodoBubbleSort	InputInt32[10000]	Média de tempo36,639,961.429 ns	Espaço alocado43 B
MétodoInsertionSort	InputInt32[100000]	Média de tempo100,408.537 ns	Espaço alocado-
MétodoBubbleSort	InputInt32[100000]	Média de tempo3,692,133,146.154 ns	Espaço alocado600 B

Em uma situação que dez elementos precisem ser ordenados, o Insertion Sort executa quatro vezes mais rápido do que o Bubble Sort. Aumentando o input para cem itens, a diferença cresce em trinta e sete vezes. Por fim, quando há uma presença de mil, dez mil e cem mil números no vetor original, o Insertion Sort entrega ganhos de trezentos e setenta e oito, três mil seiscentos e setenta e sete e trinta e seis mil setecentos e setenta e uma vezes, respectivamente.

O código-fonte dos algoritmos e os detalhes extras acerca de seus respectivos desempenhos estão disponíveis no meu repositório do Github.