Selection Sort: Como Funciona, Animação e Código em C, Python e Java

O Selection Sort, ou ordenação por seleção, procura o menor elemento da parte não ordenada e o coloca na primeira posição livre. Depois repete o processo para o segundo menor, o terceiro, e assim por diante.

Como o Selection Sort Funciona

Percorra o vetor inteiro e encontre o menor elemento.
Troque-o com o elemento da 1ª posição.
Percorra o restante (a partir da 2ª posição) e encontre o menor.
Troque-o com o elemento da 2ª posição.
Repita até a penúltima posição.

Complexidade do Selection Sort

Melhor caso	Caso médio	Pior caso	Memória extra	Estável?
O(n²)	O(n²)	O(n²)	O(1)	Não

Quando usar

Quando escrever na memória é caro: o Selection Sort faz no máximo n − 1 trocas, bem menos que o Bubble Sort. Mas sempre faz cerca de n²/2 comparações, mesmo com o vetor já ordenado.

Selection Sort em C

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

Selection Sort em Python

def selection_sort(v):
    n = len(v)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if v[j] < v[menor]:
                menor = j
        v[i], v[menor] = v[menor], v[i]
    return v

Selection Sort em Java

static void selectionSort(int[] v) {
    for (int i = 0; i < v.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < v.length; j++)
            if (v[j] < v[min]) min = j;
        int aux = v[i]; v[i] = v[min]; v[min] = aux;
    }
}

Quer comparar com outros métodos? No visualizador de algoritmos de ordenação você roda todos no mesmo vetor e compara o número de comparações e trocas.

Perguntas Frequentes

Qual a complexidade do Selection Sort?

O(n²) em todos os casos, porque ele sempre percorre toda a parte não ordenada para achar o menor, mesmo que o vetor já esteja ordenado.

O Selection Sort é estável?

Na versão tradicional, não. A troca pode passar um elemento por cima de outro igual. Exemplo: [2a, 2b, 1] vira [1, 2b, 2a].

Qual a diferença entre Selection Sort e Insertion Sort?

O Selection escolhe o menor do restante e coloca no fim da parte ordenada. O Insertion pega o próximo elemento e o insere na posição certa da parte ordenada. O Insertion é mais rápido em vetores quase ordenados.

Selection Sort: Animação Passo a Passo