Selection sort

O problema

Você precisa organizar etiquetas de preço em ordem crescente. Procura a menor de todas e a coloca no início. Depois, procura a menor entre as que sobraram e a coloca em segundo, e assim por diante.

Qual parte da sequência já está pronta depois de cada busca? Essa parte ainda pode mudar?

Faça a primeira busca em [5, 2, 4]. Quantas comparações são necessárias para ter certeza de que achou o menor?

Como funciona

O selection sort divide o vetor em duas partes: à esquerda, a parte pronta; à direita, a parte que ainda falta. Em cada etapa:

1. Seleciona. Percorre toda a parte que falta e anota a posição do menor valor.
2. Troca. Leva esse menor para o início da parte que falta, com uma única troca.
3. Avança. A parte pronta cresce uma posição.

Há um preço: para ter certeza de que achou o menor, a etapa precisa olhar todos os elementos que faltam. Não existe atalho, nem quando a lista já chega ordenada. Com 5 elementos, são sempre 4 + 3 + 2 + 1 = 10 comparações. Esse total, n(n−1)/2, é igual ao número de pares possíveis de elementos, mas cuidado: nem todo par é comparado. Cada elemento é comparado com o menor encontrado até aquele momento.

O ponto forte: poucas escritas

Cada etapa faz no máximo uma troca. Para n elementos, são no máximo n − 1 trocas, não importa quão bagunçada esteja a lista. O bubble e o insertion fazem um movimento para cada par fora de ordem, o que pode chegar a centenas de milhares de movimentos em uma lista pequena.

Dá para conferir isso com uma conta. Cada troca do selection sort escreve em 2 posições do vetor, e são no máximo n − 1 trocas: no máximo 2(n − 1) escritas. O bubble sort escreve 2 vezes o número de inversões, e o insertion sort escreve o número de inversões mais n − 1. Como cada troca do selection sort conserta pelo menos uma inversão, ele nunca escreve mais que os outros dois.

Isso importa de verdade em dois casos:

• Memória que se desgasta: memórias flash e EEPROM, comuns em microcontroladores, suportam um número limitado de escritas por posição. Escrever 250 vezes menos significa um equipamento que dura mais.
• Registros enormes: se cada elemento é uma struct de vários kilobytes, cada movimento custa caro. Poucas trocas compensam muitas comparações baratas.

Na prática

Implementação em C

void selection_sort(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {        // v[0..i-1] já está pronto
        int menor = i;                        // POSIÇÃO do menor, não o valor
        for (int j = i + 1; j < n; j++) {
            if (v[j] < v[menor]) menor = j;
        }
        if (menor != i) {                     // no máximo uma troca por etapa
            int temp = v[i];
            v[i] = v[menor];
            v[menor] = temp;
        }
    }
}

Para usar: declare int v[] = {64, 25, 12, 22, 11}; e chame selection_sort(v, 5);. O resultado é [11, 12, 22, 25, 64], com as 10 comparações e 3 trocas da figura.

Exemplo real: o pódio da corrida

Uma corrida de rua tem milhares de atletas, mas a organização precisa anunciar agora apenas os três primeiros. Ordenar todo mundo seria desperdício.

O selection sort tem uma propriedade rara: depois de k etapas, as k primeiras posições já estão prontas e definitivas. Então basta executar 3 etapas e parar:

#include <stdio.h>

typedef struct {
    char nome[20];
    float tempo;               // em segundos: menor é melhor
} Atleta;

// Deixa os k melhores tempos em a[0..k-1], em ordem. O resto fica sem ordem.
void podio(Atleta a[], int n, int k) {
    if (k > n) k = n;
    for (int i = 0; i < k; i++) {               // só k etapas
        int melhor = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j].tempo < a[melhor].tempo) melhor = j;
        }
        if (melhor != i) {
            Atleta temp = a[i];
            a[i] = a[melhor];
            a[melhor] = temp;
        }
    }
}

int main(void) {
    Atleta a[] = {
        {"Lia", 12.8f}, {"Rui", 11.9f}, {"Gil", 13.4f}, {"Bel", 11.5f},
        {"Teo", 12.1f}, {"Ivo", 12.0f}, {"Mel", 13.0f}, {"Noa", 12.4f}
    };
    int n = sizeof a / sizeof a[0];
    podio(a, n, 3);
    for (int i = 0; i < 3; i++) {
        printf("%d. %s %.1f s\n", i + 1, a[i].nome, a[i].tempo);
    }
    return 0;
}

Cada etapa percorre a lista uma vez, então o pódio custa só 3 passagens pela lista. Nos testes desta aula, o pódio de 1 milhão de atletas saiu em 10 ms. Ordenar o milhão inteiro com o selection sort levaria, pela regra do quadrado (20 vezes mais dados, 400 vezes mais tempo), cerca de 2,7 s × 400 ≈ 18 minutos, uma estimativa.

O bubble sort também tem essa propriedade, só que ao contrário: depois de k passagens, os k maiores estão prontos no fim. O insertion sort não tem: só no final se sabe quem está em primeiro.

Estabilidade: a troca de longe

O selection sort não é estável: elementos empatados podem trocar de ordem. O motivo é a troca distante. Quando o menor, ou o maior em um ranking, vem do fim do vetor, ele troca de lugar com o primeiro da parte que falta, e esse primeiro é jogado lá para trás, passando por cima de quem estava no meio.

A versão estável, à direita da figura, retira o escolhido e desloca os elementos do meio uma posição, como no insertion sort:

typedef struct {
    char nome[20];
    float nota;
} Aluno;

// Ranking estável: maior nota primeiro; empatados mantêm a ordem original.
void selection_estavel(Aluno v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int melhor = i;
        for (int j = i + 1; j < n; j++)
            if (v[j].nota > v[melhor].nota) melhor = j;   // > estrito: o primeiro dos empatados
        Aluno escolhido = v[melhor];
        for (int k = melhor; k > i; k--) v[k] = v[k - 1];   // desliza, em vez de trocar
        v[i] = escolhido;
    }
}

Com a entrada da figura (Ana 8.5, Caio 8.5, Bia 9.0), o resultado é Bia, Ana, Caio.

O preço é perder justamente a vantagem de poucas escritas: os deslocamentos voltam a ser tantos quanto no insertion sort. Se você precisa de estabilidade, use o insertion sort de uma vez.

Quanto custa na prática?

Medimos as três ordenações da revisão com as mesmas listas de 50 000 números:

1. Mesmo tempo nos três casos medidos. O selection sort levou 2,7 s nas três entradas, inclusive com a lista já ordenada, que os outros dois resolvem em uma passagem. O número de comparações é exatamente o mesmo, 1,25 bilhão, em qualquer entrada. O tempo ainda pode variar um pouco com a máquina e os dados.
2. Escritas: o menor número entre os três. Cerca de 100 mil escritas contra centenas de milhões. Entre estas três implementações, ele nunca escreve mais que as outras e costuma escrever muito menos em listas bagunçadas. Se escrever for o gargalo, ele é o melhor dos três, embora não seja o mínimo absoluto que um algoritmo qualquer poderia atingir.
3. Parar cedo é a carta na manga. Os 3 primeiros de 1 milhão saíram em 10 ms, como no pódio.

Comparação com as outras ordenações da revisão

Qual usar?

Exercícios progressivos

Use a figura do passo a passo como modelo: marque o trecho onde a etapa procura, o menor encontrado e a troca. A dica não entrega a resposta: ela indica a pergunta certa a fazer.

for (int i = 0; i < n - 1; i++) {
    int menor = v[i];
    for (int j = i + 1; j < n; j++)
        if (v[j] < menor) menor = v[j];
    v[i] = menor;
}

void selection_rec(int v[], int n) {
    if (n <= 1) return;                      // 0 ou 1 elemento: já ordenado
    int maior = 0;
    for (int j = 1; j < n; j++) {
        if (v[j] > v[maior]) maior = j;
    }
    if (maior != n - 1) {                    // o maior vai para o fim
        int temp = v[maior];
        v[maior] = v[n - 1];
        v[n - 1] = temp;
    }
    selection_rec(v, n - 1);                 // ordena o resto
}