Classificação por seleção: Algoritmo explicado com Python Exemplo de Código

O que é classificação por seleção?

CLASSIFICAÇÃO DE SELEÇÃO é um algoritmo de classificação por comparação usado para classificar uma lista aleatória de itens em ordem crescente. A comparação não requer muito espaço extra. Requer apenas um espaço de memória extra para a variável temporal.

Isso é conhecido como no lugar Ordenação. A ordenação por seleção tem uma complexidade de tempo de O(n²) onde n é o número total de itens na lista. A complexidade de tempo mede o número de iterações necessárias para classificar a lista. A lista é dividida em duas partições: a primeira lista contém itens classificados, enquanto a segunda lista contém itens não classificados.

Por padrão, a lista classificada está vazia e a lista não classificada contém todos os elementos. A lista não classificada é então verificada em busca do valor mínimo, que é então colocado na lista classificada. Este processo é repetido até que todos os valores tenham sido comparados e classificados.

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

O primeiro item da partição não classificada é comparado com todos os valores do lado direito para verificar se é o valor mínimo. Se não for o valor mínimo, então sua posição é trocada pelo valor mínimo.

Exemplo

Por exemplo, se o índice do valor mínimo for 3, então o valor do elemento com índice 3 será colocado no índice 0, enquanto o valor que estava no índice 0 será colocado no índice 3. Se o primeiro elemento na partição não classificada for o valor mínimo, então ele retorna suas posições.
O elemento que foi determinado como o valor mínimo é então movido para a partição do lado esquerdo, que é a lista ordenada.
O lado particionado agora possui um elemento, enquanto o lado não particionado possui (n – 1) elementos onde n é o número total de elementos na lista. Este processo é repetido indefinidamente até que todos os itens tenham sido comparados e classificados com base em seus valores.

Definição de problema

Uma lista de elementos que estão em ordem aleatória precisa ser classificada em ordem crescente. Considere a lista a seguir como exemplo.

A lista acima deve ser classificada para produzir os seguintes resultados

Solução (Algoritmo)

Passo 1) Obtenha o valor de n que é o tamanho total do array

Passo 2) Particione a lista em seções classificadas e não classificadas. A seção classificada está inicialmente vazia enquanto a seção não classificada contém a lista inteira

Passo 3) Escolha o valor mínimo da seção não particionada e coloque-o na seção classificada.

Passo 4) Repita o processo (n – 1) vezes até que todos os elementos da lista tenham sido classificados.

Representação visual

Dada uma lista de cinco elementos, as imagens a seguir ilustram como o algoritmo de classificação por seleção itera pelos valores ao classificá-los.

A imagem a seguir mostra a lista não classificada

Passo 1)

O primeiro valor 21 é comparado com os demais valores para verificar se é o valor mínimo.

3 é o valor mínimo, portanto as posições 21 e 3 são trocadas. Os valores com fundo verde representam a partição classificada da lista.

Passo 2)

O valor 6, que é o primeiro elemento na partição não classificada, é comparado com o restante dos valores para descobrir se existe um valor inferior

O valor 6 é o valor mínimo, portanto mantém sua posição.

Passo 3)

O primeiro elemento da lista não ordenada com valor 9 é comparado com os demais valores para verificar se é o valor mínimo.

O valor 9 é o valor mínimo, portanto mantém sua posição na partição ordenada.

Passo 4)

O valor 33 é comparado com o restante dos valores.

O valor 21 é inferior a 33, portanto as posições são trocadas para produzir a nova lista acima.

Passo 5)

Só nos resta um valor na lista não particionada. Portanto, já está classificado.

A lista final é como a mostrada na imagem acima.

Programa de classificação de seleção usando Python 3

O código a seguir mostra a implementação da classificação por seleção usando Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Execute o código acima produz os seguintes resultados

[3, 6, 9, 21, 33]

Explicação do código

A explicação do código é a seguinte

Aqui está a explicação do código:

Define uma função chamada selectionSort
Obtém o número total de elementos na lista. Precisamos disso para determinar o número de passagens a serem feitas ao comparar valores.
Laço externo. Usa o loop para iterar pelos valores da lista. O número de iterações é (n – 1). O valor de n é 5, então (5 – 1) nos dá 4. Isso significa que as iterações externas serão realizadas 4 vezes. Em cada iteração, o valor da variável i é atribuído à variável minValueIndex
Laço interno. Usa o loop para comparar o valor mais à esquerda com os outros valores do lado direito. No entanto, o valor de j não começa no índice 0. Começa em (i + 1). Isso exclui os valores que já foram classificados para que nos concentremos nos itens que ainda não foram classificados.
Encontra o valor mínimo na lista não classificada e o coloca em sua posição adequada
Atualiza o valor de minValueIndex quando a condição de troca é verdadeira
Compara os valores dos números de índice minValueIndex e i para ver se eles não são iguais
O valor mais à esquerda é armazenado em uma variável temporal
O valor inferior do lado direito ocupa a posição primeira posição
O valor que foi armazenado no valor temporal é armazenado na posição que era anteriormente mantida pelo valor mínimo
Retorna a lista ordenada como resultado da função
Cria uma lista el que contém números aleatórios
Imprima a lista ordenada após chamar a função Sort de seleção passando el como parâmetro.

Complexidade temporal da classificação de seleção

A complexidade de classificação é usada para expressar o número de tempos de execução necessários para classificar a lista. A implementação possui dois loops.

O loop externo que escolhe os valores um por um da lista é executado n vezes, onde n é o número total de valores na lista.

O loop interno, que compara o valor do loop externo com o restante dos valores, também é executado n vezes, onde n é o número total de elementos na lista.

Portanto, o número de execuções é (n * n), que também pode ser expresso como O(n²).

A classificação por seleção possui três categorias de complexidade, a saber;

Pior caso – é aqui que a lista fornecida está em ordem decrescente. O algoritmo executa o número máximo de execuções que é expresso como [Big-O] O(n²)
Melhor caso – isso ocorre quando a lista fornecida já está ordenada. O algoritmo executa o número mínimo de execuções que é expresso como [Big-Omega] ?(n²)
Caso médio – isso ocorre quando a lista está em ordem aleatória. A complexidade média é expressa como [Big-theta] ?(n²)

A classificação por seleção tem uma complexidade de espaço de O(1), pois requer uma variável temporal usada para troca de valores.

Quando usar a classificação por seleção?

A classificação por seleção é melhor usada quando você deseja:

Você deve classificar uma pequena lista de itens em ordem crescente
Quando o custo de troca de valores é insignificante
Também é usado quando você precisa ter certeza de que todos os valores da lista foram verificados.

Vantagens da classificação por seleção

A seguir estão as vantagens da classificação de seleção

Funciona muito bem em listas pequenas
É um algoritmo local. Não requer muito espaço para classificação. Apenas um espaço extra é necessário para armazenar a variável temporal.
Ele funciona bem em itens que já foram classificados.

Desvantagens da classificação por seleção

A seguir estão as desvantagens da classificação por seleção.

Ele tem um desempenho ruim ao trabalhar em listas enormes.
O número de iterações feitas durante a classificação é n ao quadrado, onde n é o número total de elementos na lista.
Outros algoritmos, como o quicksort, apresentam melhor desempenho em comparação com a ordenação por seleção.

Resumo

A classificação por seleção é um algoritmo de comparação no local usado para classificar uma lista aleatória em uma lista ordenada. Tem uma complexidade de tempo de O(n²)
A lista é dividida em duas seções, classificada e não classificada. O valor mínimo é escolhido na seção não classificada e colocado na seção classificada.
Isso se repete até que todos os itens tenham sido classificados.
Implementando o pseudocódigo em Python 3 envolve o uso de dois loops for e instruções if para verificar se a troca é necessária
A complexidade de tempo mede o número de etapas necessárias para classificar a lista.
A complexidade de tempo do pior caso ocorre quando a lista está em ordem decrescente. Tem uma complexidade de tempo de [Big-O] O(n²)
A complexidade de tempo no melhor caso ocorre quando a lista já está em ordem crescente. Tem uma complexidade de tempo de [Big-Omega] ?(n²)
A complexidade de tempo do caso médio ocorre quando a lista está em ordem aleatória. Tem uma complexidade de tempo de [Big-theta] ?(n²)
A classificação por seleção é melhor usada quando você tem uma pequena lista de itens para classificar, o custo de troca de valores não importa e a verificação de todos os valores é obrigatória.
A classificação por seleção não funciona bem em listas enormes
Outros algoritmos de ordenação, como o quicksort, apresentam melhor desempenho quando comparado à ordenação por seleção.