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;