TOP 25 ALGORITMOS | Selection Sort Array

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]) {
          
              // Atualiza 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

Como há dois loops aninhados, um loop para selecionar um elemento do array um por um (O(n)) e outro loop para comparar esse elemento com todos os outros elementos do array (O(n)), a complexidade de tempo será: O(n) ∙ O(n) = O(n ∙ n) = O(n²)

📦 | Complexidade de Espaço

A complexidade de espaço é constante, ou seja, O(1).

✔️ | Vantagens

✦ Fácil de entender e implementar, tornando-o ideal para ensinar conceitos básicos de classificação;

✦ Requer menos número de trocas (ou gravações de memória) em comparação a muitos outros algoritmos padrão;

❌ | Desvantagens

✦ Mais lenta em comparação a algoritmos como Quick Sort ou Merge Sort;

✦ Não preserva a ordem relativa de itens com chaves iguais, o que significa que não é estável;