Ordenação por seleção
A ordenação por seleção ordena uma lista como muitas pessoas ordenam as cartas na mão: encontrar a menor, pô-la em primeiro lugar e depois encontrar a menor das restantes. Faz muitas comparações mas muito poucas trocas, e o seu tempo de execução quase não depende da ordem da lista.
A ideia
Divida a lista numa parte ordenada à esquerda, vazia no início, e numa parte não ordenada à direita. Percorra a parte não ordenada e memorize onde está o seu menor valor. Troque esse valor com o primeiro valor não ordenado: a parte ordenada cresceu um valor. Repita até restar só um valor, que tem de ser o maior.
Um exemplo
Pegue em 5, 1, 4, 2, 8. A primeira passagem percorre os cinco valores, encontra o 1 como o menor e troca-o com o 5: 1, 5, 4, 2, 8. A segunda passagem percorre 5, 4, 2, 8, encontra o 2 e troca-o com o 5: 1, 2, 4, 5, 8. A terceira passagem encontra o 4 já no lugar, e a quarta encontra o 5 já no lugar, por isso nada se move. São 4 + 3 + 2 + 1 = 10 comparações e só 2 trocas. O bubble sort precisa de 4 trocas na mesma lista.
Sempre o mesmo número de comparações
Para ter a certeza de qual é o menor valor, a procura tem de olhar para todos os valores que restam. A passagem 1 faz n − 1 comparações, a passagem 2 faz n − 2, e assim por diante até 1, o que dá n(n − 1)/2. Este número não depende da lista: uma lista ordenada custa exatamente tantas comparações como uma invertida. A ordenação por seleção não tem paragem antecipada, porque uma procura que encontra o menor valor já à frente não ficou a saber nada sobre o resto.
Poucas trocas
Cada passagem faz no máximo uma troca, por isso a ordenação por seleção nunca faz mais de n − 1 trocas, e salta a troca quando o menor valor já está no lugar. O bubble sort e o insertion sort fazem tantas trocas quantos os pares fora de ordem, o que pode chegar a cerca de n²/2. Quando escrever um valor é muito mais caro do que ler dois, por exemplo numa memória que se desgasta a cada escrita, o pequeno número de trocas é uma vantagem.
Não é estável
Uma ordenação é estável quando os valores iguais mantêm a ordem original. A ordenação por seleção não é, porque uma troca a longa distância pode levar um valor para lá de outro igual. Em 2, 2, 1, a primeira passagem troca o primeiro 2 com o 1, o que dá 1, 2, 2 com os dois 2 agora pela ordem inversa. Uma versão que desloca os valores intermédios em vez de trocar é estável, mas move muitos mais valores.
Experimente
Abra a aplicação e prima Reproduzir, ou prima Avançar para ir uma comparação de cada vez. O valor a ser examinado está destacado, o menor valor até agora tem a sua própria cor, e cada passagem termina com uma troca para a parte ordenada à esquerda. Experimente uma lista ordenada e uma invertida: as comparações são iguais, só as trocas mudam.
Perguntas frequentes
Qual é a complexidade temporal da ordenação por seleção?
O(n²) em todos os casos: exatamente n(n − 1)/2 comparações para n valores, seja qual for a ordem. Faz no máximo n − 1 trocas e só precisa de O(1) de memória adicional.
Qual é a diferença entre a ordenação por seleção e o bubble sort?
O bubble sort troca vizinhos à medida que avança e pode parar mais cedo quando uma passagem não faz trocas. A ordenação por seleção só memoriza onde está o menor valor e faz uma troca no fim de cada passagem. A ordenação por seleção faz menos trocas; o bubble sort é mais rápido em listas quase ordenadas.
A ordenação por seleção é estável?
Não. Uma troca pode mover um valor para lá de outro valor igual, por isso valores iguais podem mudar de ordem. Pode tornar-se estável deslocando os valores em vez de os trocar, o que custa mais movimentos.
Qual é a ligação entre o heapsort e a ordenação por seleção?
O heapsort é uma ordenação por seleção com uma forma mais rápida de encontrar o valor seguinte: mantém a parte não ordenada num heap, por isso cada seleção leva cerca de log n passos em vez de uma procura completa. Isso reduz o total para O(n log n).
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar a ordenação por seleção