Como falamos sobre diferentes algoritmos de classificação, hoje aprenderemos sobre o algoritmo de classificação por seleção. Um algoritmo de classificação que permite a quantidade mínima possível de trocas em um ambiente com memória restrita.

Índice

1. Introdução
2. O que é algoritmo de classificação por seleção?
3. Como funciona a classificação por seleção?
   • Complexidade de tempo
   • Complexidade Espacial
4. Implementação em JavaScript
5. Resolvendo problemas de LeetCode
6. Conclusão

Introdução

A classificação por seleção é um algoritmo de classificação simples, mas eficaz, que funciona selecionando repetidamente o menor (ou maior) elemento da parte não classificada da lista e movendo-o para o início (ou final) da parte classificada. Este processo é repetido até que toda a lista esteja ordenada. Neste artigo, iremos nos aprofundar nos detalhes do algoritmo de classificação por seleção, sua implementação em JavaScript e suas aplicações na solução de problemas do mundo real.

O que é algoritmo de classificação por seleção?

O algoritmo de classificação por seleção é um algoritmo de classificação por comparação no local. Ele divide a lista de entrada em duas partes:

1. A parte classificada na extremidade esquerda
2. A parte não classificada na extremidade direita

O algoritmo seleciona repetidamente o menor elemento da parte não classificada e o troca pelo elemento não classificado mais à esquerda, movendo o limite entre as partes classificadas e não classificadas um elemento para a direita.

Como funciona a classificação por seleção?

Vamos ver um exemplo usando o array [64, 25, 12, 22, 11]:

1. Matriz inicial: [64, 25, 12, 22, 11]

• Porção classificada: []
• Porção não classificada: [64, 25, 12, 22, 11]

1. Primeira passagem:

• Encontre o mínimo na porção não classificada: 11
• Troque 11 pelo primeiro elemento não classificado (64)
• Resultado: [11, 25, 12, 22, 64]
• Porção classificada: [11]
• Porção não classificada: [25, 12, 22, 64]

1. Segunda passagem:

• Encontre o mínimo na porção não classificada: 12
• Troque 12 pelo primeiro elemento não classificado (25)
• Resultado: [11, 12, 25, 22, 64]
• Porção classificada: [11, 12]
• Porção não classificada: [25, 22, 64]

1. Terceira passagem:

• Encontre o mínimo na porção não classificada: 22
• Troque 22 pelo primeiro elemento não classificado (25)
• Resultado: [11, 12, 22, 25, 64]
• Porção classificada: [11, 12, 22]
• Porção não classificada: [25, 64]

1. Quarta passagem:

• Encontre o mínimo na porção não classificada: 25
• 25 já está na posição correta
• Resultado: [11, 12, 22, 25, 64]
• Porção classificada: [11, 12, 22, 25]
• Porção não classificada: [64]

1. Passe final:
   • Resta apenas um elemento, ele fica automaticamente na posição correta
   • Resultado final: [11, 12, 22, 25, 64]

A matriz agora está totalmente classificada.

Complexidade de tempo

Selection Sort tem uma complexidade de tempo de O(n^2) em todos os casos (melhor, média e pior), onde n é o número de elementos na matriz. Isso ocorre porque:

• O loop externo é executado n-1 vezes
• Para cada iteração do loop externo, o loop interno é executado n-i-1 vezes (onde i é a iteração atual do loop externo)

Isso resulta em aproximadamente (n^2)/2 comparações en trocas, o que simplifica para O(n^2).

Devido a essa complexidade de tempo quadrática, a classificação por seleção não é eficiente para grandes conjuntos de dados. Porém, sua simplicidade e o fato de realizar o mínimo possível de trocas podem torná-lo útil em determinadas situações, principalmente quando a memória auxiliar é limitada.

Complexidade Espacial

Selection Sort tem uma complexidade de espaço de O(1) porque classifica a matriz no local. Requer apenas uma quantidade constante de espaço de memória adicional, independentemente do tamanho da entrada. Isso o torna eficiente em termos de memória, o que pode ser vantajoso em ambientes com restrição de memória.

Implementação em JavaScript

Aqui está uma implementação JavaScript do algoritmo de classificação por seleção:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i 


Vamos detalhar o código:

Definimos uma função selectionSort que recebe um array como entrada.
Iteramos o array com o loop externo (i), que representa o limite entre as partes classificadas e não classificadas.
Para cada iteração, assumimos que o primeiro elemento não classificado é o mínimo e armazenamos seu índice.
Em seguida, usamos um loop interno (j) para encontrar o elemento mínimo real na parte não classificada.
Se encontrarmos um elemento menor, atualizamos minIndex.
Depois de encontrar o mínimo, trocamos-o pelo primeiro elemento não classificado, se necessário.
Repetimos esse processo até que todo o array esteja classificado.

  
  
  Resolvendo problemas de LeetCode


Vamos resolver um problema de algoritmo leetcode usando algoritmo de classificação por seleção. Devemos nós?

  
  
  Problema: classificar um array [médio]


Problema: Dado um array de números inteiros, classifique o array em ordem crescente e retorne-o. Você deve resolver o problema sem usar nenhuma função integrada na complexidade de tempo O(nlog(n)) e com a menor complexidade de espaço possível.

Abordagem:: Para resolver este problema, podemos aplicar diretamente o algoritmo Selection Sort. Isso envolve iterar pela matriz, encontrar o menor elemento na parte não classificada e trocá-lo pelo primeiro elemento não classificado. Repetimos esse processo até que todo o array esteja classificado.

Solução:

// This function sorts an array of integers in ascending order using the Selection Sort algorithm.
const sortArray = function (nums) {
  // Get the length of the input array.
  const n = nums.length;

  // Iterate through the array, starting from the first element.
  for (let i = 0; i 


Esta solução aplica diretamente o algoritmo Selection Sort que implementamos anteriormente. Embora resolva o problema corretamente, é importante notar que esta solução pode exceder o limite de tempo para grandes entradas no LeetCode devido à complexidade de tempo O (n ^ 2) da classificação por seleção. A imagem abaixo mostra que a solução está correta, mas não é eficiente.



  
  
  Conclusão


Concluindo, Selection Sort é um algoritmo de classificação simples e intuitivo que serve como uma excelente introdução ao mundo das técnicas de classificação. Sua simplicidade facilita a compreensão e a implementação, tornando-o uma valiosa ferramenta de aprendizado para iniciantes. No entanto, devido à sua complexidade de tempo quadrática O(n^2), não é eficiente para grandes conjuntos de dados. Para conjuntos de dados maiores ou aplicativos de desempenho crítico, algoritmos mais eficientes como QuickSort, MergeSort ou funções de classificação integradas são preferidos.


  
  
  Fique atualizado e conectado


Para garantir que você não perca nenhuma parte desta série e para se conectar comigo para obter mais detalhes

discussões sobre Desenvolvimento de Software (Web, Servidor, Mobile ou Scraping/Automação), dados

estruturas e algoritmos e outros tópicos interessantes de tecnologia, siga-me em:



    
      

        
    
  

    

A grande solução ?Siga

    

      Engenheiro de Software | Redator Técnico | Desenvolvedor de back-end, Web e dispositivos móveis? | Apaixonado por criar soluções de software eficientes e escaláveis. #vamosconectar?
    
  

• GitHub
• Linkedin
• X (Twitter)

Fique ligado e boa programação ?‍??