Selection sort
Conceito
Selection Sort é um algoritmo de ordenação baseado em comparação. Ele ordena uma
lista selecionando repetidamente o menor ou maior ( dependendo da necessidade de
ordenação) elemento da parte não ordenada e trocando-o com o primeiro elemento da
parte não ordenada da lista até que toda a lista esteja ordenada na ordem que se deseja.
Como funciona
1. Percorre a parte não ordenada da lista para encontrar o menor ou maior
(dependendo da necessidade de ordenação) valor.
2. Move o valor encontrado para a frente da parte não ordenada da lista.
3. Repete a primeira e asegunda regras até que a lista esteja totalmente ordenada .
Representação Gráfica.
23 12 6 7 3 -1 2
-1 12 6 7 3 23 2
-1 2 6 7 3 23 12
-1 12 3 7 6 23 12
-1 2 3 6 7 23 12
-1 2 3 6 7 12 23
Implementação em C
Complexidade
O algoritmo de ordenação Selection Sort tem complexidade de tempo quadrática, ou
seja, O(n²). Isso significa que o tempo de execução do algoritmo aumenta
exponencialmente com o tamanho da lista.
Vantagens da classificação por seleção
Fácil de entender e implementar, o que o torna ideal para ensinar conceitos
básicos de classificação.
Requer apenas um espaço de memória extra constante O(1).
Desvantagens da Seleção de Classificação
A classificação por seleção tem uma complexidade de tempo de O(n^2), o que a
torna mais lenta em comparação a algoritmos com Quick Sort ou Marget Sort .
Não mantém a ordem relativa de elementos iguais, o que significa que não é
estável.
Referência bibliográfica
Bhargava, A. Entendendo algoritmos ( um guia ilustrado para
programadores e outros curiosos ).Novatec Editora.2017.
[Link]