Dificuldade ★☆☆
2 minutos de Leitura 🕒
O Selection Sort (Ordenação por Seleção) é um algoritmo de ordenação que funciona selecionando o menor elemento de um arranjo e colocando-o na primeira posição, depois selecionando o segundo menor elemento e colocando-o na segunda posição, e assim sucessivamente até que o arranjo esteja ordenado.
A inicialmente vazio que contém os elementos já ordenados, e (i) um sub-arranjo B com inicialmente todos os elementos do arranjo original.B e coloque-o na última posição do sub-arranjo A.B não estiver vazio, volte ao Passo 2.A, que contém os elementos do arranjo original ordenados de forma ascendente.O pior caso para o algoritmo Selection Sort ocorre quando o arranjo de elementos já está ordenado de forma inversa. Nessa situação, o algoritmo tem um custo quadrático de comparações e um custo linear de trocas, em função do número de elementos a serem ordenados:
O(n²) comparaçõesO(n) trocasO melhor caso para o algoritmo Selection Sort ocorre quando o arranjo de elementos já está ordenado. Nessa situação, o algoritmo tem um custo quadrático de comparações e um custo constante de trocas, em função do número de elementos a serem ordenados:
O(n²) comparaçõesO(1) trocasO Selection Sort se destaca em relação aos outros algoritmos de ordenação em dois pontos: (i) por realizar um número mínimo de trocas, e (ii) não necessitar de uma estrutura de dados auxiliar para funcionar.
Por esses motivos, o Selection Sort é indicado para a ordenação de arranjos quando memória extra disponível para uso é escassa, ou então o custo para trocar-se elementos de posição no arranjo é elevado.
Veja o código completo no GitHub.