Ordenação por seleção
Encontra o menor valor que falta ordenar e troca-o para a posição seguinte. Faz muito poucas trocas, mas sempre o mesmo número de comparações.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- não
- sim
Melhor caso: como o tempo cresce com o tamanho n da lista quando a entrada é a mais fácil para este algoritmo.
Caso médio: como o tempo costuma crescer com n. Com n², o dobro de valores demora cerca de quatro vezes mais; n log n cresce bem menos.
Pior caso: o crescimento com a entrada mais difícil. Útil quando a velocidade nunca pode cair.
Memória: quanta memória extra é necessária além da lista. 1 significa algumas variáveis; n, uma cópia da lista.
Estável: dois valores iguais mantêm a ordem original. Importa quando se ordena por um só campo de um registo.
Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- a comparar
- a mover
- mínimo atual
- na posição final
Experimente: Escolha uma lista invertida. O número de comparações é exatamente o mesmo que em qualquer outra lista.
Como funciona
Procura o menor valor na parte por ordenar e troca-o com o primeiro valor dessa parte. Assim, mais um valor fica na posição final. Verifica sempre todos os valores que faltam, mesmo que a lista já esteja ordenada.
Quando é uma boa escolha
Útil quando mover dados custa caro e lê-los é barato, porque faz no máximo uma troca por posição. Na maioria dos outros casos, a ordenação por inserção é a melhor escolha simples.