|
| 1 | +# Insertion Sort |
| 2 | + |
| 3 | +#### Declaração do problema |
| 4 | + |
| 5 | +Dado um array de n elementos, escreva uma função para classificar o array em ordem crescente. |
| 6 | + |
| 7 | +#### Abordagem |
| 8 | + |
| 9 | +- Defina um índice de "chave", o subarray à esquerda do qual é classificado. |
| 10 | +- Inicie a "chave" como 1, ou seja. o segundo elemento da matriz (como há apenas um elemento à esquerda do segundo elemento, que pode ser considerado como uma matriz classificada com um elemento). |
| 11 | + |
| 12 | +- Se o valor do elemento na posição (chave - 1) for menor que o valor do elemento na posição (chave); incremento "chave". |
| 13 | +- Caso contrário, mova os elementos do subarray classificado que são maiores que o valor do elemento na "chave" para uma posição à frente de sua posição atual. Coloque o valor do elemento em "chave" no vazio recém-criado. |
| 14 | + |
| 15 | +#### Complexidade de tempo |
| 16 | + |
| 17 | +`О(n^2)` comparações, `О(n^2)` swaps - Pior caso |
| 18 | + |
| 19 | +Comparações `O(n)`, swaps `O(1)` - Melhor Caso |
| 20 | + |
| 21 | +#### Complexidade de espaço |
| 22 | + |
| 23 | +`O(1)` - (sem espaço extra necessário, classificação feita no local) |
| 24 | + |
| 25 | +#### Exemplo |
| 26 | + |
| 27 | +``` |
| 28 | +12, 11, 13, 5, 6 |
| 29 | +
|
| 30 | +Vamos fazer um loop de i = 1 (segundo elemento da matriz) para 4 (Tamanho da matriz de entrada) |
| 31 | +
|
| 32 | +i = 1. |
| 33 | +Como 11 é menor que 12, mova 12 e insira 11 antes de 12 |
| 34 | +11, 12, 13, 5, 6 |
| 35 | +
|
| 36 | +i = 2. |
| 37 | +13 permanecerá em sua posição, pois todos os elementos no subarray classificado são menores do que 13 |
| 38 | +11, 12, 13, 5, 6 |
| 39 | +
|
| 40 | +i = 3. |
| 41 | +5 moverá para o início, |
| 42 | +e todos os outros elementos de 11 a 13 se moverão uma posição à frente de sua posição atual. |
| 43 | +5, 11, 12, 13, 6 |
| 44 | +
|
| 45 | +i = 4. |
| 46 | +6 se moverá para a posição após 5, |
| 47 | +e os elementos de 11 a 13 se moverão uma posição à frente de sua posição atual. |
| 48 | +5, 6, 11, 12, 13 - matriz classificada |
| 49 | +``` |
| 50 | + |
| 51 | +#### Links de implementação de código |
| 52 | + |
| 53 | +- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/InsertionSort.java) |
| 54 | +- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/insertion_sort.c) |
| 55 | +- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/sorting/insertion_sort.cpp) |
| 56 | +- [C#](https://github.com/TheAlgorithms/C-Sharp/blob/master/Algorithms/Sorters/Comparison/InsertionSorter.cs) |
| 57 | +- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Sort/InsertionSort.scala) |
| 58 | +- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py) |
| 59 | +- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/sorting/insertion_sort.rb) |
| 60 | + |
| 61 | +#### Explicação em vídeo |
| 62 | + |
| 63 | +[Um vídeo CS50 explicando o algoritmo de pesquisa de inserção](https://www.youtube.com/watch?v=DFG-XuyPYUQ) |
0 commit comments