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 da 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):
para x no intervalo (len (minhalista) - 1, 0, -1):
max_idx = 0
para posn no intervalo (1, x + 1):
if mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = minha lista [x]
minha lista [x] = minha lista [max_idx]
minha lista [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
para (int x = 0; x { 
índice interno = x; 
para (int y = x + 1; y if (my_array [y] índice = y; // encontre o índice mais baixo 
} 
} 
int temp = my_array [índice]; // temp é um armazenamento temporário
my_array [index] = my_array [x]; 
minha_matriz [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 classificaçã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.

Sobre o autor