5.8. A Ordenação Por Seleção¶

A ordenação por seleção melhora o bubble sort ao realizar apenas uma troca a cada passagem pela lista. Para conseguir isso, uma ordenação por seleção procura pelo valor mais alto enquanto faz uma passagem e, depois de completá-la, coloca-o na posição correta. Assim como o bubble sort, depois da primeira passagem, o maior item sempre está na posição correta. Depois da segunda passagem, o próximo maior item também vai para a posição adequada. O processo continua dessa forma e demanda \(n-1\) passagens para ordenar n itens, já que o item final deverá estar no lugar certo depois da \((n-1)\)-ésima passagem.

A Figura 3 mostra o processo de ordenação completo. A cada passagem, o maior item remanescente é selecionado e colocado no lugar apropriado. A primeira passagem posiciona o 93, a segunda, o 77, a terceira, o 55, e assim por diante. A função é mostrada no ActiveCode 1.

Figura 3: Ordenação Por Seleção¶

Você pode ver que a ordenação por seleção faz o mesmo número de comparações que o bubble sort e também é \(O(n^{2})\). Contudo, devido à redução do número de trocas, a ordenação por seleção tipicamente executa mais rápido em análises de desempenho. Na verdade, para a nossa lista, o bubble sort realiza 20 trocas, enquanto a ordenação por seleção faz apenas 8.