Estrutura de Dados
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Ir para baixo
avatar
henrique19
Admin
Admin
Mensagens : 4
Pontos : 14
Reputação : 2
Data de inscrição : 05/05/2017

Seletion Sort Empty Seletion Sort

Sáb Nov 25, 2017 1:26 pm
Reputação da mensagem: 100% (1 votos)
Definição

A ordenação por seleção (do inglês, selection sort) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os {\displaystyle n-1} n-1 elementos restantes, até os últimos dois elementos.

O selection sort compara a cada interação um elemento com os outros, visando encontrar o menor. Dessa forma, podemos entender que não existe um melhor caso mesmo que o vetor esteja ordenado ou em ordem inversa serão executados os dois laços do algoritmo, o externo e o interno. A complexidade deste algoritmo será sempre O(n^{2} enquanto que, por exemplo, os algoritmos heapsort e mergesort possuem complexidades O(n log n).

Vantagens

- Ele é um algoritmo simples de ser implementado em comparação aos demais.
- Não necessita de um vetor auxiliar (in-place).
- Por não usar um vetor auxiliar para realizar a ordenação, ele ocupa menos memória.
- Ele é uns dos mais velozes na ordenação de vetores de tamanhos pequenos.

Desvantagens

- Ele é um dos mais lentos para vetores de tamanhos grandes.
- Ele não é estável.
- Ele faz sempre {\displaystyle n^{2}} n^2 comparações, independente do vetor está ordenado ou não.

Implementação do método Selection Sort

Código:
void selectionSort( int vetorDesordenado[], int tamanhoVetor )
{
   int i, j, posicaoValorMinimo;

   for (i = 0; i < ( tamanhoVetor - 1 ); i++)
   {
      posicaoValorMinimo = i;
      for (j = ( i + 1 ); j < tamanhoVetor; j++)
      {
         if( vetorDesordenado[j] < vetorDesordenado[posicaoValorMinimo] )
         {
           posicaoValorMinimo = j;
         }
       }
      
       if ( i != posicaoValorMinimo )
       {
          trocarPosicaoValores( &vetorDesordenado[i], &vetorDesordenado[posicaoValorMinimo] );  
       }
   }
}

Vídeos para reforços (ABRA O SPOILER):

Atividade de Fixação (ABRA O SPOILER):
Ir para o topo
Tópicos semelhantes
Permissões neste sub-fórum
Não podes responder a tópicos