- henrique19Admin
- Mensagens : 4
Pontos : 14
Reputação : 2
Data de inscrição : 05/05/2017
Seletion Sort
Sáb Nov 25, 2017 1:26 pm
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
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):
Permissões neste sub-fórum
Não podes responder a tópicos
|
|