# Algoritmo de classificação por inserção
Visão geral
A classificação por inserção é um algoritmo de classificação simples que funciona inserindo cada elemento de um array em sua posição correta no array. Ele começa com um array classificado vazio e depois percorre o array de entrada, inserindo cada elemento em sua posição correta no array classificado. Este processo é repetido até que todo o array de entrada seja classificado.
Etapas do algoritmo
Aqui está o algoritmo passo a passo para classificação por inserção:
1. Comece com um array classificado vazio.
2. Itere pela matriz de entrada.
3. Para cada elemento da matriz de entrada, insira-o em sua posição correta na matriz classificada.
4. Para inserir um elemento, compare-o com cada elemento do array ordenado, começando pelo primeiro elemento.
5. Se o elemento for menor que o elemento atual na matriz classificada, insira-o antes do elemento atual.
6. Se o elemento for maior que o elemento atual na matriz classificada, continue comparando com o próximo elemento na matriz classificada.
7. Repita as etapas 4 a 6 até que o elemento seja inserido em sua posição correta na matriz classificada.
8. Repita as etapas 2 a 7 para cada elemento da matriz de entrada.
Exemplo
Vamos considerar a seguinte matriz de entrada:
```
[5, 2, 8, 3, 1]
```
As etapas a seguir mostram como o algoritmo de classificação por inserção classificaria essa matriz:
1. Comece com um array classificado vazio.
```
[]
```
2. Itere pela matriz de entrada.
```
[5]
```
3. Para cada elemento da matriz de entrada, insira-o em sua posição correta na matriz classificada.
```
[5]
```
4. Para inserir o elemento 2, compare-o com cada elemento do array ordenado, começando pelo primeiro elemento.
```
[5, 2]
```
5. Como 2 é menor que 5, insira-o antes do elemento atual.
```
[2, 5]
```
6. Itere pela matriz de entrada.
```
[2, 5, 8]
```
7. Para cada elemento da matriz de entrada, insira-o em sua posição correta na matriz classificada.
```
[2, 5, 8]
```
8. Para inserir o elemento 3, compare-o com cada elemento do array ordenado, começando pelo primeiro elemento.
```
[2, 3, 5, 8]
```
9. Como 3 é menor que 5, insira-o antes do elemento atual.
```
[2, 3, 5, 8]
```
10. Itere pela matriz de entrada.
```
[2, 3, 5, 8, 1]
```
11. Para cada elemento da matriz de entrada, insira-o em sua posição correta na matriz classificada.
```
[1, 2, 3, 5, 8]
```
12. Para inserir o elemento 1, compare-o com cada elemento do array ordenado, começando pelo primeiro elemento.
```
[1, 2, 3, 5, 8]
```
13. Como 1 é menor que 2, insira-o antes do elemento atual.
```
[1, 2, 3, 5, 8]
```
14. A matriz classificada está completa.
```
[1, 2, 3, 5, 8]
```
Complexidade de tempo
A complexidade de tempo da classificação por inserção é O (n ^ 2), onde n é o comprimento da matriz de entrada. Isso significa que o tempo de execução da classificação por inserção aumenta quadraticamente à medida que o tamanho da matriz de entrada aumenta. A classificação por inserção tem melhor desempenho quando a matriz de entrada já está quase classificada; nesse caso, sua complexidade de tempo é O (n).
Complexidade Espacial
A ordenação por inserção requer espaço auxiliar O(1), pois só precisa armazenar uma única variável (o elemento atual que está sendo inserido) além do array de entrada.
Vantagens e Desvantagens
A classificação por inserção tem algumas vantagens e desvantagens:
Vantagens: * Simples de implementar
* Eficiente para matrizes pequenas ou matrizes quase classificadas
* Algoritmo de classificação estável (mantém a ordem relativa de elementos iguais)
Desvantagens: * Não é eficiente para grandes arrays
* Complexidade de tempo quadrática (O(n^2))
* Não é um algoritmo de classificação local (requer espaço adicional)
Conclusão
A classificação por inserção é um algoritmo de classificação simples e eficiente que funciona bem para matrizes pequenas ou quase ordenadas. Sua simplicidade e estabilidade fazem dele um algoritmo útil para fins educacionais e para aplicações especializadas. No entanto, não é o algoritmo de classificação mais eficiente para matrizes grandes, onde algoritmos mais eficientes, como quicksort ou merge sort, deveriam ser usados.
