O Insertion Sort (ordenação por inserção) é um dos algoritmos de ordenação quadráticos mais populares, ao lado do Selection Sort e do Bubble Sort.
![Algoritmo de ordenação por inserção Insertion Sort](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguFeaXrKYdKc2yvVCBuxYgLIbcNy7j3UQTOPn4pf9sJDEPNEgyGSADX302n1gGumZ3iy8LxKHp_erGbCyhutWy09pSNz4XAdTELw6O6dnAxBilIh7p954nUUvnq3gB0eYqdV5S_Cf7VIPm/w960/insertion-sort.jpg)
Assim como seus "irmãos", o tempo de execução do Insertion Sort no pior caso e no caso médio é $O(n^2)$. Entretanto, o seu tempo no melhor caso é linear, que é um dos destaques do algoritmo.
Nesta postagem, analisaremos o Insertion Sort apresentado no livro "Algoritmos: teoria e prática". O algoritmo também será disponibilizado nas linguagens Java, C e JavaScript.
Índice
Funcionamento do Insertion Sort
O Insertion Sort inicia a ordenação dividindo o vetor em duas partições: uma ordenada à esquerda e outra não ordenada à direita. Inicialmente, a partição esquerda só terá um elemento (é o caso trivial da ordenação).
A inserção dos elementos na partição ordenada é realizada em duas etapas. Na primeira etapa, procuramos a posição de inserção. Na segunda etapa, deslocamos os elementos da esquerda para a direita para que a posição de inserção fique livre para que o elemento seja inserido.
Faremos essas duas etapas simultaneamente. O pseudocódigo é [1]
//algoritmo adaptado o livro "Algoritmos: teoria e prática" (Cormen et al) 01. insertionSort(A[0...n-1]) 02. | para i ← 1 até n-1 03. | | elemento ← A[i] 04. | | j ← i - 1 05. | | enquanto(j ≥ 0 E A[j] > elemento) 06. | | | A[j + 1] ← A[j] //deslocamento para a direita 07. | | | j ← j - 1 08. | | fim_enquanto 09. | | A[j + 1] = elemento //insere o elemento na parte ordenada 10. | fim_para 11. fim_insertionSort
O algoritmo é bem simples. Se você preferir, pode substituir o laço enquanto
(while
) por para
(for
)
//algoritmo adaptado o livro "Algoritmos: teoria e prática" (Cormen et al) 01. insertionSort(A[0...n-1]) 02. | para i ← 1 até n - 1 03. | | elemento ← A[i] 04. | | para(j ← i - 1; j ≥ 0 E A[j] > elemento; j ← j - 1) 05. | | | A[j + 1] ← A[j] //deslocamento para a direita 06. | | fim_para 07. | | A[j + 1] = elemento //insere o elemento na parte ordenada 08. | fim_para 09. fim_insertionSort
Os dois algoritmos são equivalentes.
Exemplo
Para exemplificar o uso do algoritmo, ordenaremos o seguinte vetor
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi2SCsq-fu9uF9b46jvsW9_M9_UkmEQmD2bzT-MrGRoKb0cW7ab8hVmHFMyGhV92NPKyTWozIQ8DBXrc4WZERXsGmDCMXC6pmMk8R09sHFlNm9aI-r_GNJfcedqcW5XC5h2vR8ghJW2hxfO/s1600/vetor-01.png)
Inicialmente, temos i = 1
, j = 0
e elemento = 1
. Queremos inserir elemento na parte ordenado à esquerda. Como 3 > 1
, então deslocamos o 3 para direita e decrementamos j
: j = 0 - 1 = -1
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwWMPhY5DNDBCFph_EKFc_BnqLd1VjUA80v5E8j9x1VbFjcQy5zndCMFxbf0f6Wik57dPOltJl2oOpjdubMD5CVb4WPZYyZlRmuTucAV5HhIX3x7EaYl9piCCfLPRZwWuGvEdCWxqaqnPl/s1600/vetor-02.png)
Como atingimos o início do vetor, então inserimos 1
em j + 1 = 0
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbdfbwA-g_8-3cddl4B1nAYG5spp23ZdfBP1e1NTkm4gkzkmkMdwU__6gIIkjW25y0LWtyYAGNGgGEoAfQ2z95hmZIFcKh1b8ZXgGPshDg-HcA_683qXn1wehUkHOP9ICFETSJ4pMIkVgH/s1600/vetor-03.png)
Agora, i = 2
, j = 1
e elemento = 9
. Como 3 < 9
, então o elemento já está na posição correta (na verdade, o algoritmo insere o elemento na própria posição onde ele está).
Na terceira iteração, i = 3
, j = 2
e elemento = 5
. Como 9 > 5
, então deslocamos o 9 para direita e decrementamos j
: j = 2 - 1 = 1
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgT9D87U8JGaR_OdkVZfZEVlgMD4ZYr_TD2Xsb1gim3HcbZcEicCZrpht6YntQO7LyzEYxKyfLmRmMSbLXeAFZniEMRsgmWKpSHhDUOJ7S7xoMQy-7ZY3GANt7h3HXffAnATx5q79bwl-7c/s1600/vetor-04.png)
Como 3 < 5
, então inserimos 5
em j + 1 = 2
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEioSv233Ra7d4LtcMAM89Vt7IMhyphenhyphen7Bzu6orimVOwUPvKQGxd9O4RoDsiNxcugKrcVyiTJCL-wFtYRcD5vxQIm8iJW78Lka0FKGcUR0b-ROSqZFEvP4SSqquf_a7kaf0YcVpYTYJ4ZdXoDoP/s1600/vetor-05.png)
Na quarta iteração, i = 4
, j = 3
e elemento = 2
. Como 9 > 2
, então deslocamos o 9 para direita e decrementamos j
: j = 3 - 1 = 2
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjS30XGheC96RRosFaUJ-TmKklFhra-5rQamX5tcyc8Z0LbpO9Z9TfsbPwo31XI-ARE_GyTkDOlADp30qucKROnjq_PNpb27z-1vKdtT35fUqfHh4-ROH-KOgoa18rQ_9dFz-a9OuAzXn8/s1600/vetor-06.png)
Como 5 > 2
, então deslocamos o 5 para direita e decrementamos j
: j = 2 - 1 = 1
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge4oQYHiqn2hEUKtiq02qWZZ6XVBi424NEkxbPR7yuMG-yA5Puwjf6-Afz7EWDNPaxJUKjzEDUaFBaHC5uidNV-tAwnIqhZFgCFYxmpsQkWVANor9B0sgeRbOLzKs6R1oNeiO3QZ41GqK6/s1600/vetor-07.png)
Como 3 > 2
, então deslocamos o 3 para direita e decrementamos j
: j = 1 - 1 = 0
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMhmhr3Ip8ChQST1-M99jT4vPcjatY0ajAXZgCBqyqt22VhnNXa5nW0s_jILxRucMHhzPl23m5hBGUPQInzB7fdblpWwIT9wWuYUt5gPGej9mksEHToXbq4K3vBM8LQoMH0yj7na72iRIk/s1600/vetor-08.png)
Como 1 < 2
, então inserimos 2
em j + 1 = 1
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiIB793qUzoGG-qRTI3C335slwsLKESnXTJAk9bdfq_tPf4kriZio-5wAp2d3aFozc67j-9WhFB86wHN5rnKRT0Kr2ASXppMGT1mqm77Cxd1ibe-S7Tyj3Qp6kY1n6v6q0EJAg3fUg0uvWp/s1600/vetor-09.png)
Na quinta e última iteração, i = 5
, j = 4
e elemento = 8
. Como 9 > 8
, então deslocamos o 9 para direita e decrementamos j
: j = 4 - 1 = 3
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgheV_QHkqILLNjjrtYWh2L4laIUOHKzlnMd6cV0f4jb1kUpHwKjrvQ0sUgU30UIK_9S26-81LuHa2qH7xX96K2j2sbQEAOpDlsCCVjSbM9HAazgv_CukcsvGI8uE9LAjkwx9P9_9-HXelH/s1600/vetor-10.png)
Como 5 < 8
, então inserimos 8
em j + 1 = 4
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiDNkXdL6F70wLD6Wz9vQ7JbMi-df6hpRU4nLBge71zujK3KAhqRz51CXW5-1tg70ZJO7UxUz4fe_ful4-RHmS8h-aL3bbVBhJGhMeW3mgf6jZVRIGUrD1_DaUI7YukTM9Im4O3ckzGdpqy/s1600/vetor-11.png)
Com isso, finalizamos a ordenação.
Complexidade assintótica
O pior caso do Insertion Sort ocorre quando os elementos do vetor estão em ordem decrescente, pois a condição A[j] > elemento
sempre será verdadeira. Logo, o laço interno realizará a quantidade máxima de iterações. Nesse caso, o Insertion Sort terá complexidade no tempo de $O(n^2)$.
O melhor caso ocorre quando o vetor está ordenado, pois, ao contrário do pior caso, a condição A[j] > elemento
sempre será falsa. Logo, o código do laço interno nunca será executado. Assim, teremos apenas as n - 1
iterações do laço externo, portanto a complexidade no tempo é $O(n)$.
O caso médio do Insertion Sort é $O(n^2)$. Lembrando que o caso médio é uma média entre todas as entradas possíveis. Isso significa que, em geral, ele terá tempo quadrático, estatisticamente falando.
Códigos
Os códigos em Java, C e em JavaScript do Insertion Sort podem ser obtidos nos links a seguir
Considerações finais
O gráfico a seguir foi retirado de um antigo trabalho meu de complexidade de algoritmos da época em que eu fazia faculdade. O gráfico faz um comparativo do tempo de execução do Bubble Sort, Selection Sort e Insertion Sort.
![Gráfico de comparativo de desempenho entre Bubble Sort, Selection Sort e Insertion Sort.](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEih8Ifesj-x2KIDcqMeRnfuE5EXv_gVYg3Y5GqBMIdVD31HdHFQuon2fmfjwqk7i_cr5sBzZEhuiRA6rkt0BYcEz13yr5g1CSJCXGa8JWFKSCAoqtU42aQWhZEwGncJ0xIkMG3V_Ge8VMov/s1600/comparativo-desempenho-bubble-selection-insertion-sort.png)
O desempenho do Insertion Sort o torna uma boa opção para realizar a ordenação de vetores pequenos. Entretanto, é sempre bom lembrar que a biblioteca padrão da maioria das linguagens de programação já possui métodos que ordenam vetores. É extremamente recomendado que você utilize esses métodos, pois os algoritmos implementados são otimizados para cada linguagem.
Referências
- [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Nenhum comentário:
Postar um comentário