Selection sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Selection sort

algoritmo selection sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso total, auxiliar
Algoritmos
Animação do algoritmo 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 elementos restantes, até os últimos dois elementos.

Descrição do algoritmo[editar | editar código-fonte]

É composto por dois laços, um laço externo e outro interno. O laço externo serve para controlar o índice inicial e o interno percorre todo o vetor. Na primeira iteração do laço externo o índice começa de 0 e cada iteração ele soma uma unidade até o final do vetor e o laço mais interno percorre o vetor começando desse índice externo + 1 até o final do vetor. Isso ficará mais explícito no exemplo.

Exemplo:

vetor = 9 - 7 - 8 - 1 - 2 - 0 - 4

O primeiro laço o índice inicial é 0. O laço mais interno começa do índice 1 (índice_inicial_externo + 1) e percorre o vetor até acha o menor elemento, neste caso o número zero. O zero passa para a posição inicial do vetor que na primeira iteração do laço é 0.

0 - 7 - 8 - 1 - 2 - 9 - 4

Ao fim do laço interno o laço externo incrementa uma unidade, agora a posição inicial do vetor passa a ser 1, pois o zero já se encontra no lugar dele, não é preciso mais fazer verificações pois ele é o menor elemento deste vetor. Agora o processo se repete, buscando o segundo menor elemento, neste caso o um.

0 - 1 - 8 - 7 - 2 - 9 - 4

Consequentemente o terceiro menor, quarto menor,...

Assim sucessivamente até o vetor está ordenado.

0 - 1 - 2 -7 - 8 - 9 - 4

...

0 - 1 - 2 - 4 - 8 - 9 - 7

...

0 - 1 - 2 - 4 - 7 - 9 - 8

...

0 - 1 - 2 - 4 - 7 - 8 - 9

Complexidade[editar | editar código-fonte]

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 enquanto que, por exemplo, os algoritmos heapsort e mergesort possuem complexidades

Vantagens[editar | editar código-fonte]

  • Ele é um algoritmo simples de ser implementado em comparação aos demais.
  • Não necessita de uma 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[editar | editar código-fonte]

  • Ele é um dos mais lentos para vetores de tamanhos grandes.
  • Ele não é estável.
  • Ele faz sempre comparações, independente do vetor está ordenado ou não.

Exemplos de códigos[editar | editar código-fonte]

Implementação em C (linguagem de programação):

void selection_sort(int num[], int tam) { 
  int i, j, min, aux;
  for (i = 0; i < (tam-1); i++) 
  {
     min = i;
     for (j = (i+1); j < tam; j++) {
       if(num[j] < num[min]) 
         min = j;
     }
     if (num[i] != num[min]) {
       aux = num[i];
       num[i] = num[min];
       num[min] = aux;
     }
  }
}

Implementação em C++, colocando os menores no início:

void SelectionSort(int vetor[], int tam) {
    for (int indice = 0; indice < tam; ++indice) {
        int indiceMenor = indice;
        for (int indiceSeguinte = indice+1; indiceSeguinte < tam; ++indiceSeguinte) {
            if (vetor[indiceSeguinte] < vetor[indiceMenor]) {
                indiceMenor = indiceSeguinte;
            }
        }
        int aux = vetor[indice];
        vetor[indice] = vetor[indiceMenor];
        vetor[indiceMenor] = aux;
    }
}

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]