O que é a classificação por seleção?
SELECTION SORT é 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 classificação no local . A ordenação por seleção tem uma complexidade de tempo de O (n 2 ), 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 para o valor mínimo, que é então colocado na lista classificada. Este processo é repetido até que todos os valores tenham sido comparados e classificados.
Neste tutorial de algoritmo, você aprenderá:
- O que é a classificação por seleção?
- Como funciona a classificação por seleção?
- Definição de problema
- Solução (algoritmo)
- Representação visual
- Programa de classificação de seleção usando Python 3
- Explicação do código
- Complexidade de tempo da classificação de seleção
- Quando usar a classificação por seleção?
- Vantagens do tipo de seleção
- Desvantagens da classificação por seleção
Como funciona a classificação por seleção?
O primeiro item na partição não classificada é comparado com todos os valores à direita para verificar se é o valor mínimo. Se não for o valor mínimo, sua posição é trocada com o valor mínimo.
Exemplo:
- Por exemplo, se o índice do valor mínimo for 3, então o valor do elemento com índice 3 é colocado no índice 0, enquanto o valor que estava no índice 0 é 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 é movido para a partição do lado esquerdo, que é a lista classificada.
- O lado particionado agora tem um elemento, enquanto o lado não particionado tem (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 seguinte lista como exemplo.
[21,6,9,33,3]
A lista acima deve ser classificada para produzir os seguintes resultados
[3,6,9,21,33]
Solução (algoritmo)
Etapa 1) Obtenha o valor de n, que é o tamanho total da matriz
Etapa 2) Particionar 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
Etapa 3) Escolha o valor mínimo da seção não particionada e coloque-o na seção classificada.
Etapa 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 de seleção itera por meio dos 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, então as posições de 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 ordenada é comparado com o resto dos valores para descobrir se existe um valor inferior
O valor 6 é o valor mínimo, por isso mantém sua posição.
Etapa 3)
O primeiro elemento da lista não ordenada com o valor 9 é comparado com o resto dos valores para verificar se é o valor mínimo.
O valor 9 é o valor mínimo, portanto, ele mantém sua posição na partição classificada.
Passo 4)
O valor 33 é comparado com o resto dos valores.
O valor 21 é inferior a 33, então as posições são trocadas para produzir a nova lista acima.
Etapa 5)
Temos apenas um valor restante 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 de classificação de seleção usando Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Executar 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 da lista. Precisamos disso para determinar o número de passagens a serem feitas ao comparar valores.
- Loop 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. Ele 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 do índice minValueIndex ei para ver se eles não são iguais
- O valor mais à esquerda é armazenado em uma variável temporal
- O menor valor do lado direito assume a 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 classificada como o resultado da função
- Cria uma lista el que contém números aleatórios
- Imprime a lista classificada após chamar a função Sort da seleção, passando el como parâmetro.
Complexidade de tempo 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 a 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 2 ).
O tipo de seleção tem três categorias de complexidade, a saber;
- Pior caso - aqui é onde a lista fornecida está em ordem decrescente. O algoritmo realiza o número máximo de execuções, que é expresso como [Big-O] O (n 2 )
- Melhor caso - ocorre quando a lista fornecida já está classificada. O algoritmo realiza o número mínimo de execuções que é expresso como [Big-Omega] Ω (n 2 )
- Caso médio - isso ocorre quando a lista está em ordem aleatória. A complexidade média é expressa como [Big-theta] ⊝ (n 2 )
A ordenação por seleção tem uma complexidade espacial de O (1), pois requer uma variável temporal usada para trocar valores.
Quando usar a classificação por seleção?
A classificação de 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 se certificar de que todos os valores na lista foram verificados.
Vantagens do tipo de seleção
A seguir estão as vantagens do tipo 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 manter a variável temporal.
- Ele tem um bom desempenho em itens que já foram classificados.
Desvantagens da classificação por seleção
A seguir estão as desvantagens do tipo de seleção.
- Ele tem um desempenho ruim ao trabalhar em listas enormes.
- O número de iterações feitas durante a classificação é n-quadrado, onde n é o número total de elementos na lista.
- Outros algoritmos, como quicksort, têm melhor desempenho em comparação com a classificação por seleção.
Resumo:
- A classificação por seleção é um algoritmo de comparação local usado para classificar uma lista aleatória em uma lista ordenada. Tem uma complexidade de tempo de O (n 2 )
- A lista é dividida em duas seções, classificadas e não classificadas. O valor mínimo é escolhido na seção não classificada e colocado na seção classificada.
- Essa coisa é repetida até que todos os itens tenham sido classificados.
- A implementação do pseudocódigo no Python 3 envolve o uso de duas instruções for e if para verificar se a troca é necessária
- A complexidade do tempo mede o número de etapas necessárias para classificar a lista.
- O pior caso de complexidade de tempo ocorre quando a lista está em ordem decrescente. Tem uma complexidade de tempo de [Big-O] O (n 2 )
- A complexidade de tempo na melhor das hipóteses ocorre quando a lista já está em ordem crescente. Tem uma complexidade de tempo de [Big-Omega] Ω (n 2 )
- A complexidade de tempo médio ocorre quando a lista está em ordem aleatória. Tem uma complexidade de tempo de [Big-theta] ⊝ (n 2 )
- 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 da seleção não funciona bem em listas grandes
- Outros algoritmos de classificação, como quicksort, apresentam melhor desempenho quando comparados à classificação por seleção.