Ordenação por Selection Sort

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