Selection sort
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 | |
Esta caixa:
|
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
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[0] # 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