# Insertion sort

Insertion Sort, ou ordenação por inserção, é um algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação.
Podemos fazer uma comparação do Insertion Sort com o modo como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando ás cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma a que as cartas obedeçam à ordenação.
A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, a 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 em diante, até 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 (um). 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.

## Características

Apesar de ser menos eficiente do que algoritmos como Merge Sort e Quick Sort (de ordem O(nlog(n))), o Insertion Sort possui algumas características consideráveis:
* É de simples implementação, leitura e manutenção;
* In-place: Apenas requer uma quantidade constante de O(1) espaço de memória adicional;
* Estável: Não muda a ordem relativa de elementos com valores iguais;
* Útil para pequenas entradas;
* Muitas trocas, e menos comparações;
* Melhor caso: O(n), quando a matriz está ordenado;
* Médio caso: O(n²/4), quando a matriz tem valores aleatórios sem ordem de classificação (crescente ou decrescente);
* Pior caso: O(n²), quando a matriz está em ordem inversa, daquela que deseja ordenar.

## Análise com outros algoritmos de ordenação por comparação e troca

Em termos de comparação com outros algoritmos de ordenação, o Insert sort e o Bubble sort atingem O(n) em seus melhores casos, diferente do Selection sort que é O(n²) em todos os seus casos (melhor, médio e pior caso).
| Algoritmo | Complexidade | Complexidade | Complexidade |
| | Melhor | Médio | Pior |
| Insertion sort | O(n) | O(n$^2$) | O(n$^2$) |
| Bubble sort | O(n) | O(n$^2$) | O(n$^2$) |
| Selection sort | O(n$^2$) | O(n$^2$) | O(n$^2$) |
Obs.: O BubbleSort atinge O(n) em seu melhor caso, quando o vetor já está inteiramente ordenado! Então é necessário apenas uma verificação básica sobre todo o vetor, o que representa um custo de O(n).

## Análise Matemática

Para a ordenação de uma matriz ordenada de forma aleatória, com diferentes chaves, o algoritmo - Insertion Sort-, se utiliza de ¼ N² comparações e ½ N² trocas. $\sum _{k=1}^{i}k={\frac {(1)}{i}}{\frac {i(i+1)}{2}}={\frac {(i+1)}{2}}$
Para o caso médio, assume que todas as permutações de entrada são igualmente prováveis. Com a auxílio de funções geradoras, o caso médio do Insertion sort é equivalente a:
$B(z)=zB(z)+{\frac {z}{2}}\sum _{n=>0}kz^{k}=zB(z)+{\frac {1}{2}}{\frac {z^{2}}{(1-z)^{2}}}$, onde $B(z)$ é a função geradora correspondente ao número total de inversões.
Para o melhor caso (itens já ordenados) temos; $\sum _{i=1}^{n-1}1=n-1=O(n)$
Pior caso (itens em ordem reversa) temos: $\sum _{i=1}^{n-1}i={\frac {(n-1)(n)}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}=O(n^{2})$

## Matrizes Parcialmente Ordenadas

Realiza inversões de pares de chaves - keys - que estão fora de ordem, exemplo:
Uma matriz é parcialmente ordenado se o número de inversões é <=CN. Onde, c é o número de componentes desta matriz. Exemplo:
Para um array ou matriz parcialmente ordenado, o Insertion Sort ocorre em um tempo linear. Prova:

## Vantagens e Desvantagens
### Vantagens

* É o método a ser utilizado quando o arquivo está "quase" ordenado
* É um bom método quando se desejar adicionar poucos elementos em um arquivo já ordenado, pois seu custo é linear.
* O algoritmo de ordenação por inserção é estável.

### Desvantagens

* Alto custo de movimentação de elementos no vetor.

## Implementações
### Pseudocódigo

Segue uma versão simples do pseudocódigo do algoritmo, com vetores começando em zero:
Nessa versão é acrescentada uma verificação para saber se precisa "inserir" o "eleito" na sua nova posição, ou seja, se não houve trocas, não precisa reescrever o valor, já que ele já estará no lugar certo.

### C++

Utilizando os recursos mais recentes da linguagem é possível implementar da seguinte maneira:
Como o algoritmo toma o parâmetro vetor como referência não há sentido em retorná-lo já que ele ordena o vetor passado.

### Java

Nessa versão em Java, apresentamos o Insertion sort "in place", ou seja, a ordenação ocorre no próprio vetor.