image

Access unlimited bootcamps and 650+ courses forever

60
%OFF
Article image
Isadora Ariane
Isadora Ariane14/11/2024 09:07
Share

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

    image

    🤖 | 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;

    Share
    Comments (0)