Selection Sort
Última atualização
O selection sort divide o array em uma região ordenada à esquerda e uma região não ordenada à direita. Em cada passagem ele percorre a região não ordenada para encontrar o menor elemento e então o troca para a primeira posição não ordenada, aumentando a região ordenada em um. Pressione reproduzir acima para ver a varredura e troca, ou avance uma comparação de cada vez.
O selection sort sempre faz o mesmo número de comparações independentemente da entrada, mas realiza no máximo n-1 trocas - muito menos que o bubble sort - o que importa quando as escritas são caras.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Melhor caso | O(n²) | As comparações acontecem mesmo se já estiver ordenado |
| Caso médio | O(n²) | Ordem aleatória |
| Pior caso | O(n²) | Ordem inversa |
| Espaço | O(1) | No próprio lugar |
| Estável | Não | As trocas podem reordenar elementos iguais |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Trate todo o array como não ordenado. |
| 2 | Percorra a região não ordenada para encontrar o elemento mínimo. |
| 3 | Troque esse mínimo para a primeira posição não ordenada. |
| 4 | Mova o limite um passo à direita (essa posição já está ordenada). |
| 5 | Repita até restar apenas um elemento não ordenado. |
Exemplo resolvido
Ordenando [5, 2, 4, 1]:
| Passagem | Array | Ação |
|---|---|---|
| Início | [5, 2, 4, 1] | Todo o array está não ordenado. |
| 1 | [1, 2, 4, 5] | Percorre [5, 2, 4, 1], o mínimo é 1 no índice 3; troca com o índice 0. |
| 2 | [1, 2, 4, 5] | Percorre [2, 4, 5], o mínimo é 2 já no índice 1; troca consigo mesmo. |
| 3 | [1, 2, 4, 5] | Percorre [4, 5], o mínimo é 4 já no índice 2; nenhum movimento necessário. |
| Fim | [1, 2, 4, 5] | Resta apenas 5, então ele já está no lugar. |
Quando usar o selection sort
| Use quando | Evite quando |
|---|---|
As escritas são caras - ele faz no máximo n-1 trocas. | O array é grande - as O(n²) comparações dominam. |
| Você precisa de uma ordenação no próprio lugar simples e fácil de implementar. | Você precisa de uma ordenação estável que preserve a ordem de chaves iguais. |
A memória é limitada - ele usa apenas O(1) de espaço extra. | Os dados estão quase ordenados - ele não pode terminar antes como o insertion sort. |
| O conjunto de dados é minúsculo e o desempenho previsível importa. | A vazão importa - ordenações O(n log n) como o quicksort são muito mais rápidas. |
Código de Selection Sort
Uma implementação limpa e executável de Selection Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Selection Sort em Python
Python
1def selection_sort(a):2 n = len(a)3 for i in range(n - 1):4 # Find the smallest element in the unsorted tail5 min_idx = i6 for j in range(i + 1, n):7 if a[j] < a[min_idx]:8 min_idx = j9 a[i], a[min_idx] = a[min_idx], a[i]10 return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)Código de Selection Sort em JavaScript
JavaScript
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 // Find the smallest element in the unsorted tail5 for (let j = i + 1; j < a.length; j++) {6 if (a[j] < a[min]) min = j;7 }8 if (min !== i) [a[i], a[min]] = [a[min], a[i]];9 }10 return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));Código de Selection Sort em Java
Java
1import java.util.Arrays;2
3public class Main {4 static void selectionSort(int[] arr) {5 for (int i = 0; i < arr.length - 1; i++) {6 int minIndex = i;7 // Find the smallest value in the unsorted part8 for (int j = i + 1; j < arr.length; j++) {9 if (arr[j] < arr[minIndex]) minIndex = j;10 }11 int tmp = arr[i];12 arr[i] = arr[minIndex];13 arr[minIndex] = tmp;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {29, 10, 14, 37, 13, 5};19 System.out.println("Before: " + Arrays.toString(arr));20 selectionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Código de Selection Sort em C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11 for (size_t i = 0; i + 1 < a.size(); ++i) {12 // Find the smallest element in the unsorted suffix13 size_t minIdx = i;14 for (size_t j = i + 1; j < a.size(); ++j) {15 if (a[j] < a[minIdx]) minIdx = j;16 }17 std::swap(a[i], a[minIdx]);18 }19}20
21int main() {22 std::vector<int> data = {29, 10, 14, 37, 13, 5};23 std::cout << "Before: ";24 printVec(data);25 selectionSort(data);26 std::cout << "After: ";27 printVec(data);28 return 0;29}Código de Selection Sort em C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void selectionSort(int a[], int n) {9 for (int i = 0; i < n - 1; i++) {10 // Find the smallest element in the unsorted suffix11 int minIdx = i;12 for (int j = i + 1; j < n; j++) {13 if (a[j] < a[minIdx]) minIdx = j;14 }15 int tmp = a[i];16 a[i] = a[minIdx];17 a[minIdx] = tmp;18 }19}20
21int main(void) {22 int data[] = {29, 10, 14, 37, 13, 5};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 selectionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Perguntas frequentes sobre Selection Sort
Qual é a complexidade de tempo do selection sort?
O selection sort é
O(n²) em todos os casos - melhor, médio e pior - porque sempre percorre toda a região não ordenada para encontrar cada mínimo. Ele usa O(1) de espaço extra.O selection sort é estável?
A versão padrão no próprio lugar não é estável, porque trocar um mínimo distante para a posição pode mover um elemento igual à frente de outro. Existe uma variante estável, mas ela exige deslocar em vez de trocar.
Quando o selection sort é útil?
Ele é útil quando o custo de escrever na memória é alto, já que realiza no máximo
n-1 trocas - o mínimo possível para uma ordenação por comparação que move elementos.Qual é a diferença entre selection sort e bubble sort?
Ambos são ordenações por comparação
O(n²), mas o selection sort faz no máximo n-1 trocas enquanto o bubble sort pode fazer até O(n²) trocas. O bubble sort também pode detectar um array já ordenado e parar antes, ao passo que o selection sort sempre executa todas as passagens.Devo usar selection sort ou insertion sort?
Na maioria dos casos prefira o insertion sort - ele é estável, roda em
O(n) em dados quase ordenados e é mais rápido em média. Escolha o selection sort apenas quando minimizar o número de escritas for a prioridade, pois ele garante no máximo n-1 trocas.Por que o selection sort sempre roda em O(n²) mesmo em um array ordenado?
O selection sort não tem como saber que um elemento já é o mínimo sem percorrer o resto da região não ordenada, então realiza todas as comparações em cada passagem independentemente da ordem de entrada. Por isso o melhor caso é igual ao pior em
O(n²) - diferente do insertion ou bubble sort, que podem interromper cedo.Recursos relacionados
Mais visualizações
