Aprenda o Insertion Sort de maneira simplificada
O que são algoritmos de Sort?
Imagine que você está em uma escola primária e seu professor pediu que os alunos ficassem enfileirados de acordo com sua altura, do menor para o maior, isso é um problema de ordenação, que leva como base a altura para ordenar os alunos e no nosso caso vamos levar em consideração para simplificar a nossa ordenação valores inteiros.
Como funciona o Insertion Sort
O Insertion Sort cria uma "fatia" na sua parte esquerda que está sempre ordenada.
Considere que o primeiro item da lista já está ordenado, vamos comparar o elemento na segunda posição com o elemento a sua esquerda.
Como 50 é menor que 60 eles trocam de posição.
No caso seguinte, 40 é menor que 60 e 50 respectivamente, então 40 ocupará a primeira posição da lista.
Ao compararmos 70 com os elementos a sua esquerda vemos que ele é o maior, então permanece na mesma posição.
Por fim, como 20 é menor que todos os elementos, ele ocupará a primeira posição, empurrando todos os demais elementos para frente.
E logo, temos uma lista ordenada
Características
- É um algoritmo de fácil implementação e manutenção;
- Seu melhor caso possui complexidade O(n), quando a matriz já está ordenada [1, 2, 3, 4, 5];
- Seu pior caso possui complexidade O(n²), quando a matriz está em ordem inversa [5, 4, 3, 2, 1].
Implementação em Swift do Insertion Sort
