Menu

Classificação de seleção em C ++ com exemplos

selection sort c with examples

Experimente Nosso Instrumento Para Eliminar Problemas

Uma análise aprofundada da seleção de classificação em C ++ com exemplos.

Como o próprio nome sugere, a técnica de classificação de seleção primeiro seleciona o menor elemento da matriz e o troca pelo primeiro elemento da matriz.

Em seguida, ele troca o segundo menor elemento na matriz pelo segundo elemento e assim por diante. Portanto, para cada passagem, o menor elemento na matriz é selecionado e colocado em sua posição adequada até que toda a matriz seja classificada.

=> Confira o guia de treinamento perfeito C ++ aqui.

Ordem de Seleção

O que você aprenderá:

Introdução

A classificação por seleção é uma técnica de classificação bastante simples, pois a técnica envolve apenas encontrar o menor elemento em cada passagem e colocá-lo na posição correta.

A classificação por seleção funciona de forma eficiente quando a lista a ser classificada é pequena, mas seu desempenho é afetado gravemente à medida que o tamanho da lista a ser classificada aumenta.

Portanto, podemos dizer que a ordenação por seleção não é aconselhável para listas de dados maiores.

Algoritmo Geral

O Algoritmo Geral para classificação de seleção é fornecido abaixo:

python selênio encontrar elemento por texto

Ordenação por Seleção (A, N)

Passo 1 : Repita as etapas 2 e 3 para K = 1 a N-1
Passo 2 : Chame a rotina menor (A, K, N, POS)
etapa 3 : Troque A (K) por A (POS)
(Fim do loop)
Passo 4 : SAÍDA

Rotina menor (A, K, N, POS)

  • Passo 1 : (inicializar) definir smallestElem = A (K)
  • Passo 2 : (inicializar) definir POS = K
  • etapa 3 : para J = K + 1 a N -1, repetir
    if smallestElem> A (J)
    definir smallestElem = A (J)
    definir POS = J
    (se acabar)
    (Fim do loop)
  • Passo 4 : retorno POS

Pseudocódigo para classificação por seleção

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

Um exemplo para ilustrar esse algoritmo de classificação de seleção é mostrado abaixo.

Ilustração

Ilustração de classificação de seleção

Pass2

Pass3

Pass4

A representação tabular para esta ilustração é mostrada abaixo:

Lista não classificadaMínimo elementoLista ordenada
{18,10,7,20,2}dois{}
{18,10,7,20}7{dois}
{18,10,20}10{2.7}
{18,20}18{2,7,10)
{vinte}vinte{2,7,10,18}
{}{2,7,10,18,20}

A partir da ilustração, vemos que a cada passagem, o próximo menor elemento é colocado em sua posição correta na matriz classificada. Na ilustração acima, vemos que, para classificar uma matriz de 5 elementos, foram necessárias quatro passagens. Isso significa que, em geral, para classificar um array de N elementos, precisamos de N-1 passes no total.

Dada a seguir é a implementação do algoritmo de classificação de seleção em C ++.

Exemplo C ++

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

Resultado:

Lista de entrada de elementos a serem classificados

11 5 2 20 42 53 23 34 101 22

A lista ordenada de elementos é

2 5 11 20 22 23 34 42 53 101

Número de passes necessários para classificar a matriz: 10

Conforme mostrado no programa acima, começamos a classificação por seleção comparando o primeiro elemento do array com todos os outros elementos do array. No final desta comparação, o menor elemento da matriz é colocado na primeira posição.

Na próxima passagem, usando a mesma abordagem, o próximo menor elemento na matriz é colocado em sua posição correta. Isso continua até N elementos, ou até que todo o array seja classificado.

Exemplo de Java

A seguir, implementamos a técnica de classificação de seleção na linguagem Java.

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

Resultado:

Lista de entrada a ser classificada ...

11 5 2 20 42 53 23 34 101 22

imprimindo elementos classificados ...

2 5 11 20 22 23 34 42 53 101

Também no exemplo de java acima, aplicamos a mesma lógica. Encontramos repetidamente o menor elemento do array e o colocamos no array ordenado até que todo o array esteja completamente ordenado.

Assim, a ordenação por seleção é o algoritmo mais simples de implementar, pois temos apenas que encontrar repetidamente o próximo menor elemento na matriz e trocá-lo com o elemento em sua posição apropriada.

Análise de complexidade do tipo de seleção

Como visto no pseudocódigo acima para ordenação por seleção, sabemos que a ordenação por seleção requer dois loops for aninhados um com o outro para se completar. Um loop for percorre todos os elementos do array e encontramos o índice mínimo do elemento usando outro loop for aninhado dentro do loop for externo.

Portanto, dado um tamanho N da matriz de entrada, o algoritmo de ordenação de seleção tem os seguintes valores de tempo e complexidade.

Pior caso de complexidade de tempoO (n2); O (n) swaps
Melhor caso de complexidade de tempoO (n2); O (n) swaps
Complexidade de tempo médioO (n2); O (n) swaps
Complexidade do espaçoO (1)

A complexidade de tempo de O ( n dois) é principalmente devido ao uso de dois loops for. Observe que a técnica de ordenação por seleção nunca leva mais do que O (n) swaps e é benéfica quando a operação de gravação de memória se mostra cara.

Conclusão

A classificação por seleção é outra técnica de classificação mais simples que pode ser facilmente implementada. A classificação por seleção funciona melhor quando o intervalo dos valores a serem classificados é conhecido. Portanto, no que diz respeito à classificação de estruturas de dados usando a classificação por seleção, só podemos classificar estruturas de dados lineares e de tamanho finito.

Isso significa que podemos classificar com eficiência estruturas de dados como matrizes usando a classificação por seleção.

Neste tutorial, discutimos a classificação por seleção em detalhes, incluindo a implementação da classificação por seleção usando as linguagens C ++ e Java. A lógica por trás da classificação de seleção é encontrar o menor elemento na lista repetidamente e colocá-lo na posição adequada.

No próximo tutorial, aprenderemos em detalhes sobre a classificação por inserção, que é considerada uma técnica mais eficiente do que as outras duas técnicas que discutimos até agora, ou seja, classificação por bolha e classificação por seleção.

=> Verifique aqui para ver os tutoriais de treinamento A-Z de C ++ aqui.

Leitura recomendada

^