TOP 25 ALGORITMOS | Insertion Sort
É um algoritmo de classificação simples que funciona inserindo iterativamente cada elemento de uma lista não classificada em sua posição correta em uma parte classificada da lista. É como classificar cartas de baralho em suas mãos. Você divide as cartas em dois grupos: as cartas classificadas e as cartas não classificadas. Então, você escolhe uma carta do grupo não classificado e a coloca no lugar certo no grupo classificado.
📁 | Resumo
🤖 | Código
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
/* Move elementos de arr[0..i-1], que são maiores que key, para uma posição à frente de sua posição atual */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
🕰️ | Complexidade de Tempo
✦ Melhor Cenário: se a lista já estiver classificada, ou seja, ordenada, O(n);
✦ Cenário Comum: se a lista estiver classificada de forma aleatória, O(n²);
✦ Pior Cenário: se a lista estiver classificada de forma reversa (decrescente), O(n²);
📦 | Complexidade de Espaço
A classificação por inserção requer espaço adicional, o que a torna um algoritmo de classificação com uso eficiente de espaço. Logo, a complexidade de espaço será de O(1).
✔️ | Vantagens
✦ Simples e fácil de implementar;
✦ Algoritmo de classificação estável;
✦ Eficiente para listas pequenas e listas quase classificadas;
✦ Eficiente em termos de espaço, pois é um algoritmo no local;
✦ O número de inversões é diretamente proporcional ao número de trocas (swaps).
❌ | Desvantagens
✦ Ineficiente para listas grandes;