Prévia do material em texto

Definição
O Selection Sort é o algoritmo de ordenação que organiza os dados que estão aleatoriamente bagunçados de forma crescente ou decrescente, não muito eficiente para uma grande quantidades de dados pois faz seu processo através de comparação tornando-o lento.
Introdução
Neste trabalho iremos apresentar o método de ordenação selection sort ou seleção.
Este método é o mais simples possível dentre os possíveis meios de ordenação. O selection sort ou seleção é muito utilizado para ordenar pequenas quantidades de elementos.
A lógica consistem em percorrer todos os elementos da cadeia comparando cada elemento entre-si, sempre buscando o menor elemento da ordem. 
Principais vantagens e desvantagens.
No método de ordenação por selection sort temos como principais vantagens:
Custo linear no tamanho da entrada para o número de movimentos de registros.
É muito interessante para arquivos pequenos.
Podemos citar ainda as principais desvantagens do método:
O fato de o arquivo já estar ordenado não ajuda em nada, pois o custo continua quadrático. 
O algoritmo não é estável, pois ele nem sempre deixa os registros com chaves iguais na mesma posição relativa.
Ordenação por Seleção (Selection Sort)
Ideia Básica: Neste processo de ordenação, pretende-se utilizado o método mais simples possível, na qual se percorre o conjunto de elementos a ordenar e procura-se o maior/menor elemento do conjunto. Estando este elemento já ordenado, procura-se o segundo maior/menor elemento, e assim por diante até obter-se todos os elementos ordenados.
Método: Neste método, pretende-se ordenar os elementos de um array, que vão ser ordenados desde a primeira posição até à última posição, na qual em cada iteração da ordenação é calculado o maior/menor (maior elemento para ordenação por ordem decrescente, menor caso contrário) valor dos elementos que ainda faltam ordenar. O processo repete-se até que todos os elementos do array estejam ordenados.
Para ordenar os seguintes dados por ordem crescente, processa-se do seguinte modo:
Algoritmo:
1. Iniciar achando o menor elemento.
2. Trocar o menor elemento pelo primeiro. “Parte do vetor está agora ordenada”.
3. Achar o menor elemento da parte não ordenada.
4. Troque com o primeiro elemento da parte não ordenada
“Adicionar mais um número à parte ordenada”.
5. Aumentar o tamanho da parte ordenada em um elemento.
6. Voltar ao passo 3
“Pode-se parar quando a parte não ordenada tem apenas um número, sendo este o maior elemento”.
Eficiência
Tempos de Ordenação (sendo N o número de elementos a ordenar)
• Melhor caso = N (dados já ordenados), dado que o ciclo interno nunca ser executado, pois a sua condição falha sempre.
• Média = N²
• Pior caso = N² (Dados ordenados em ordem inversa), sendo N o número de elementos do array, o ciclo mais abrangente deverá ser executado N vezes, e o ciclo interno será executado N vezes por cada ciclo mais abrangente.
Não é difícil verificar que o algoritmo de seleção, tal como o de inserção, faz cerca de n2 comparações entre elementos do vetor.
Implementação em C++
void SelectionSort (int array[], int num_elem)
{
for (int i = 0; i < num_elem -1; i++)
{
int min = i;
for (int j = i; j < num_elem -1; j++)
{
if (a ray[j] < array[min])
{ min = j; }
}
int temp = array[min];
array[min] = array[i];
array[i] = temp;
}
}
Implementação em Java
public static void SelectionSort(int[] v) {
int index_min, aux;
for (int i = 0; i < v.length; i++) {
index_min = i;
for (int j = i + 1; j < v.length; j++) {
if (v[j] < v[index_min]) {
index_min = j; }
}
if (index_min != i) {
aux = v[index_min];
v[index_min] = v[i];
v[i] = aux; }
}
}
Exemplo:
Array com 10 elementos a ordenar por ordem crescente.
1º passo de ordenação:
Menor elemento: dados [3] que é colocado na posição dados [0]
2º passo de ordenação:
Menor elemento: dados [5] que é colocado na posição dados [1]
3º passo de ordenação:
Menor elemento: dados [2] que é colocado na posição dados [2]
4º passo de ordenação:
Menor elemento: dados [5] que é colocado na posição dados [3]
5º passo de ordenação:
Menor elemento: dados [5] que é colocado na posição dados [4]
O processo repete-se até que todos os elementos do array estejam ordenados.
Conclusão:
Conforme exposto no trabalho foi observado que o método de ordenação por selection sort, é o mais indicado para problemas com pouca quantidade de elementos, sendo ineficaz e extremamente demorado para grandes quantidades de elementos.
No método de ordenação por selection sort, são varridos sucessivos elementos que se encontram desordenados, retirando o elemento da lista e depois insere o elemento na posição correta.
Referências.
“Ordenação pelos métodos insertion e selection sort.” Disponível em:
http://www.manfred.com.br/index.php/bsi/estrutura-de-dadosii/154-aula-03-ordenacao-pelos-metodos-insertion-sort-eselection-sort Acessado em: 11/11/2020.
“Ordenando Vetores Usando Linguagem C.” Disponível em: http://terminaldeinformacao.com/2013/05/10/ordenandovetores-usando-linguagem-c/
Acessado em: 11/11/2020.
BOSS, Silvio. “Métodos de Ordenação: Ordenação por Bolha, Seleção Direta e Inserção.” Disponível em: http://www.slideshare.net/alessandrot91/aula16-metodosordenacaonovo Acessado em: 11/11/2020.
“Algoritmos por Selecção (Selection Sort)” Disponível em:
http://www.estig.ipbeja.pt/~rmcp/estig/2002/1s/lp2/teorica/sele
ctionsort.pdf Acessado em: 11/11/2020.