Comparações
Trocas
Passagem

  • Comparados
  • Mínimo até agora
  • Trocados
  • No lugar

Mais sobre a ordenação por seleção

Ordenação por seleção

A ordenação por seleção constrói a lista ordenada a partir do início. Cada passagem percorre os valores ainda não ordenados, guarda o menor e leva-o com uma troca para a primeira posição não ordenada. Reproduza a ordenação a qualquer velocidade, ou avance uma comparação de cada vez, e acompanhe os contadores de comparações, trocas e passagens. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Os contadores mostram comparações, trocas e passagens. Escolha quantas barras, como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
  3. Veja o menor valor até agora mudar à medida que a procura avança, e a troca que o coloca no lugar no fim de cada passagem.

Como funciona a ordenação por seleção

Olhe para todos os valores da lista e memorize o menor. Troque-o com o primeiro valor: a primeira posição fica definitiva. Depois faça o mesmo com o resto da lista, começando uma posição mais à frente. Após n − 1 passagens, todos os valores estão no lugar, e o último fica no lugar por exclusão.

Muitas comparações, poucas trocas

A procura nunca para mais cedo, porque só depois de olhar para todos os valores restantes pode ter a certeza de qual é o menor. Por isso, a ordenação por seleção faz exatamente n(n − 1)/2 comparações para n valores, quer a lista esteja ordenada, invertida ou aleatória. Em contrapartida, faz no máximo n − 1 trocas, uma por passagem. Isso torna-a uma escolha razoável quando mover um valor custa muito mais do que comparar dois.

Perguntas frequentes

Como funciona a ordenação por seleção?

Seleciona repetidamente o menor valor ainda não ordenado e leva-o com uma troca para a primeira posição não ordenada. Após a passagem k, as primeiras k posições têm os k menores valores por ordem.

Quantas comparações e trocas faz a ordenação por seleção?

Sempre n(n − 1)/2 comparações para n valores: 45 para 10 valores, 780 para 40. O número de trocas é no máximo n − 1, uma por passagem, e menos quando o menor valor já está no lugar.

Porque é que uma lista ordenada demora tanto como uma invertida?

Porque cada passagem tem de olhar para todos os valores restantes para ter a certeza de que encontrou o menor. Ao contrário do bubble sort e do insertion sort, a ordenação por seleção não consegue perceber pelas comparações que a lista já está ordenada.

A ordenação por seleção é estável?

Não nesta forma habitual. Uma troca pode levar um valor para lá de outro igual: em 2, 2, 1, o primeiro 2 troca com o 1 e acaba atrás do segundo 2. Uma versão que desloca os valores em vez de os trocar é estável, à custa de mais movimentos.

Os meus números são enviados para algum lado?

Não. A ordenação corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor