Abrir menu principal
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 algoritmoEditar

É 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é achar 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

ComplexidadeEditar

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  

VantagensEditar

  • 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.

DesvantagensEditar

  • 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ódigosEditar

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;
    }
}

Implementação em Python 3.7, utilizando funções:

 1 # coding: utf - 8
 2 
 3 list = []  # Definindo de um array
 4 
 5 # função para que o usuario digite os numeros desejados
 6 def choose_elements():
 7     for i in range(0, 5, 1):                      # Escolha de um range até 5 posições, porém pode ser alterado
 8         list.append(int(input("Type number: ")))  # Acrescente valores ao array, que terá o tamanho do range escolhido
 9     print(list)                                   # exibição dos valores como forma de verificação
10 
11 # função que executa a ordenação dos valores através de selection sort
12 def selection_sort(list):
13     for i in range(len(list)):                   # Laço externo
14         smaller = i                              # Atribui na variavel o valor do indice a ser verificado
15         for j in range(i + 1, len(list)):        # Laço interno que verifica se o valor anterior é menor que o próximo valor
16             if list[j] < list[smaller]:          # Verifica se o valor anterior é menor que o próximo valor
17                 smaller = j                      # Caso sim, variavel recebe o indice que compõe o menor valor
18         if list[i] != list[j]:                   # Se valores são iguais não é necessaria a troca
19             aux = list[i]                        # Variavel aux recebe o valor que está no indice i
20             list[i] = list[smaller]              # O indice i recebe o valor do indice j, que possui o valor menor
21             list[smaller] = aux                  # O indice da frente recebe valor do indice anterior,o maior na comparação
22 
23 choose_elements()                                # Chama a função para escolha dos numeros
24 selection_sort(list)                             # Chama a função para ordenar, como parametro o array list
25 print(list)                                      # Exibe os valores de forma ordenada

Ver tambémEditar

Ligações externasEditar