thumb|250px|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 É 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
Complexidade
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 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 comparações, independentemente do vetor estar ordenado ou não.
Implementações C 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 (i != min) { aux = num[i]; num[i] = num[min]; num[min] = aux;
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;
C# void SelectionSort(int[] vetor) { int min, aux; for (int i = 0; i < vetor.Length-1; i++)
min = i; for (int j = (i+1); j < vetor.Length; j++)
if (vetor[j] < vetor[min])
min = j;
if (vetor[i] != vetor[min])
aux = vetor[i]; vetor[i] = vetor[min]; vetor[min] = aux;
Python def selection_sort(lista): """ Ordena uma lista. Custo O(n²) """
n = len(lista) # tamanho da lista
if n == 1: # caso base return lista
# Loop externo para iterar sobre os índices da lista for i in range(n-1):
menor = i # primeiro índice inicia como o menor
# Loop interno para encontrar o índice do menor elemento for j in range(i + 1, n): if lista[j] < lista[menor]: menor = j
# Se o elemento atual não é o menor, troca if lista[i] != lista[menor]: aux = lista[i] lista[i] = lista[menor] lista[menor] = aux
return lista
# USO lista_desordenada = [3,2,1] # Lista de números desordenados lista_ordenada = selection_sort(lista_desordenada) # ordena print(lista_ordenada) # [1, 2, 3] V // Loop
fn selection_sort_loop<T>(mut array_to_sort []T, compare fn (a T, b T) bool) { array_to_sort_len := array_to_sort.len
for i in 0..array_to_sort_len { // index of lowest mut ilo := i
for j in i + 1..array_to_sort_len { if compare(array_to_sort[ilo], array_to_sort[j]) { ilo = j
//if i != ilo { array_to_sort[i], array_to_sort[ilo] = array_to_sort[ilo], array_to_sort[i] /*tmp := array_to_sort[i] array_to_sort[i] = array_to_sort[ilo] array_to_sort[ilo] = tmp*/ //}
fn selection_sort_loop_clone<T>(array_to_sort []T, compare fn (a T, b T) bool) []T { mut array_to_sort_clone := array_to_sort.clone()
selection_sort_loop<T>(mut array_to_sort_clone, compare)
return array_to_sort_clone }
// Recursion
fn selection_sort_recursion<T>(mut array_to_sort []T, compare fn (a T, b T) bool) { array_to_sort_len := array_to_sort.len
//if array_to_sort_len <= 1 { return }
// index of lowest i := 0 mut ilo := i
for j in i + 1..array_to_sort_len { if compare(array_to_sort[ilo], array_to_sort[j]) { ilo = j
//if i != ilo { array_to_sort[i], array_to_sort[ilo] = array_to_sort[ilo], array_to_sort[i] /*tmp := array_to_sort[i] array_to_sort[i] = array_to_sort[ilo] array_to_sort[ilo] = tmp*/ //}
if i + 1 < array_to_sort_len { selection_sort_recursion<T>(mut array_to_sort[i + 1..], compare)
fn selection_sort_recursion_clone<T>(array_to_sort []T, compare fn (a T, b T) bool) []T { mut array_to_sort_clone := array_to_sort.clone()
selection_sort_recursion<T>(mut array_to_sort_clone, compare)
return array_to_sort_clone }
// Selection Sort
enum LoopRec { loop recursion }
fn selection_sort<T>(mut array_to_sort []T, compare fn (a T, b T) bool, loop_rec LoopRec) { match loop_rec { .loop { selection_sort_loop<T>(mut array_to_sort, compare) } .recursion { selection_sort_recursion<T>(mut array_to_sort, compare) }
fn selection_sort_clone<T>(array_to_sort []T, compare fn (a T, b T) bool, loop_rec LoopRec) []T { return match loop_rec { .loop { selection_sort_loop_clone<T>(array_to_sort, compare) } .recursion { selection_sort_recursion_clone<T>(array_to_sort, compare) }
Ver também Algoritmo de ordenação Quick sort Merge sort Bubble sort Heapsort Pesquisa binária
Ligações externas Sorting algorithms/Selection sort - Implementação do algoritmo em várias linguagens de programação
Categoria:Algoritmos de ordenação