TOP 25 ALGORITMOS | Selection Sort

É um algoritmo de classificação baseado em comparação. Ele classifica um array selecionando repetidamente o menor (ou maior) elemento da porção não classificada e trocando-o com o primeiro elemento não classificado. Esse processo continua até que o array inteiro seja classificado.

📁 | Resumo

🤖 | Código

function selectionSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {

      // Assuma que a posição atual é válida o elemento mínimo
      let min_idx = i;

      // Iterar pela parte não classificada para encontrar o mínimo real
      for (let j = i + 1; j < n; j++) {
          if (arr[j] < arr[min_idx]) {

              // Atualizar min_idx se um elemento menor for encontrado
              min_idx = j;
          }
      }

      // Move o elemento mínimo para seu posição correta
      let temp = arr[i];
      arr[i] = arr[min_idx];
      arr[min_idx] = temp;
  }
}

🕰️ | Complexidade de Tempo
O tempo de execução de um algoritmo cresce de forma quadrática em relação ao tamanho da entrada n. Em outras palavras, se o tamanho da entrada dobra, o tempo de execução pode quadruplicar. Logo, sua complexidade de tempo será descrita por O(n²).

📦 | Complexidade de Espaço
Requer apenas um espaço de memória extra constante. Logo, sua complexidade de espaço será descrita por O(1).

✔️ | Vantagens
✦ Fácil de entender e implementar;
✦ Requer apenas um espaço de memória extra constante O(1);
✦ Requer menos número de swaps (ou gravações de memória) em comparação a muitos outros algoritmos padrão;

❌ | Desvantagens
✦ Processamento lento;
✦ Não mantém a ordem relativa de elementos iguais;
✦ Não preserva a ordem relativa de itens com chaves iguais, o que significa que é instável;