Ordenação por Selection Sort

Páginas: 3 (544 palavras) Publicado: 28 de outubro de 2013
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 eprocura-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étodoNeste 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 (maiorelemento 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.
Paraordenar 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 dovetor 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 otamanho 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 deOrdenaçã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 maisabrangente.
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...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • ALGORITMOS DE ORDENAÇÃO BUBBLE SORT e SELECTION SORT
  • Comparação entre os algoritmos de ordenação de dados: buble sort, quick sort, selection sort, inserction sort,...
  • selection sort
  • Selection sort
  • SELECTION SORT
  • Selection sort
  • Selection Sort
  • SELECTION SORT

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!