Como usar a classificação por seleção

A classificação por seleção é uma técnica de classificação que seleciona um item da lista e, em seguida, troca seu lugar por outro. Ele seleciona o maior item e, em seguida, o troca por um item no índice mais alto da lista.

O algoritmo faz isso repetidamente até que a lista seja classificada. Se você não tem certeza de como a classificação de seleção funciona, você veio ao lugar certo. Explicaremos com mais detalhes abaixo, além de mostrar um exemplo.

Classificação de seleção: um olhar mais atento

Suponha que você tenha a lista: [39, 82, 2, 51, 30, 42, 7]. Para classificar a lista usando a classificação por seleção, você teria que primeiro encontrar o número mais alto nela.

Com a lista fornecida, esse número é 82. Troque 82 pelo número do índice mais alto (ou seja, 7).

Após a primeira passagem, a nova ordem da lista será: [39, 7, 2, 51, 30, 42, 82]. Cada vez que o algoritmo passa por toda a lista, isso é chamado de "aprovação".

Observe que a lista mantém uma sublista classificada e uma sublista não classificada durante o processo de classificação.

Relacionado: O que é notação Big-O?

A lista original começa com uma lista classificada de zero itens e uma lista não classificada de todos os itens. Então, após a primeira passagem, ele tem uma lista classificada contendo apenas o número 82.

Na segunda passagem, o número mais alto na sublista não classificada será 51. Este número será trocado por 42 para dar a nova ordem da lista abaixo:

[39, 7, 2, 42, 30, 51, 82].

O processo é repetido até que toda a lista seja classificada. A figura abaixo resume todo o processo:

Os números em negrito preto mostram o valor de lista mais alto naquele momento. Aqueles em verde mostram a sublista classificada.

Análise de Algoritmo

Para obter a complexidade (usando a notação Big-O) deste algoritmo, siga as instruções abaixo:

Na primeira passagem, (n-1) comparações são feitas. Na segunda passagem, (n-2). Na terceira passagem, (n-3) e assim por diante até a (n-1) ésima passagem que faz apenas uma comparação.

Resumindo as comparações a seguir:

(n-1) + (n-1) + (n-1) + … + 1 = ((n-1) n) / 2.

Portanto, a classificação de seleção é O (n ² ).

Implementação de Código

O código mostra funções que você pode usar para realizar a classificação de seleção usando Python e Java.

Pitão:

 def selectionSort(mylist):
 for x in range(len(mylist) - 1, 0, -1):
 max_idx = 0
 for posn in range(1, x + 1):
 if mylist[posn] > mylist[max_idx]:
 max_idx = posn
 temp = mylist[x]
 mylist[x] = mylist[max_idx]
 mylist[max_idx] = temp

Java:

 void selectionSort(int my_array[]){
 for (int x = 0; x < my_array.length - 1; x++)
 {
 int index = x;
 for (int y = x + 1; y < my_array.length; y++){
 if (my_array[y] < my_array[index]){
 index = y; // find lowest index
 }
 }
 int temp = my_array[index]; // temp is a temporary storage
 my_array[index] = my_array[x];
 my_array[x] = temp;
 }}

Movendo-se da classificação por seleção para a classificação por fusão

Como a análise do algoritmo acima mostrou, o algoritmo de ordenação de seleção é O (n ² ). Ele tem uma complexidade exponencial e, portanto, é ineficiente para conjuntos de dados muito grandes.

Um algoritmo muito melhor para usar seria a classificação por mesclagem com uma complexidade de O (nlogn). E agora que você sabe como funciona a classificação por seleção, o próximo item em sua lista de estudos para algoritmos de classificação deve ser a classificação por mesclagem.