selection sort java selection sort algorithm examples
Este tutorial explicará tudo sobre a classificação de seleção em Java juntamente com o algoritmo de classificação de seleção, código Java, implementação em Java e exemplos de Java:
A técnica de ordenação por seleção é um método no qual o menor elemento da matriz é selecionado e trocado pelo primeiro elemento da matriz. Em seguida, o segundo menor elemento da matriz é trocado pelo segundo elemento e vice-versa.
=> Verifique aqui para ver A-Z dos tutoriais de treinamento de Java aqui.
O que você aprenderá:
Classificação de seleção em Java
Desta forma, o menor elemento na matriz é selecionado repetidamente e colocado em sua posição adequada até que toda a matriz seja classificada.
Duas submatrizes são mantidas para classificação de seleção:
- Submatriz classificada: Em cada iteração, o elemento mínimo é encontrado e colocado em sua posição adequada. Esta submatriz é classificada.
- Submatriz não classificada: Os elementos restantes não são classificados.
A classificação por seleção é uma técnica de classificação direta e fácil. A técnica envolve apenas encontrar o menor elemento em cada passe e colocá-lo na posição correta. A classificação de seleção é ideal para conjuntos de dados menores, pois classifica o conjunto de dados menor com eficiência.
Assim, podemos dizer que a classificação por seleção não é aconselhável para listas de dados maiores.
Algoritmo de classificação de seleção
O Algoritmo Geral para Classificação por Seleção é fornecido abaixo:
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 smallestItem = A (K)
Passo 2 : (inicializar) definir POS = K
etapa 3 :
para J = K + 1 a N -1, repita
if smallestItem> A (J)
definir smallestItem = A (J)
definir POS = J
(se acabar)
(Fim do loop)
Passo 4 : retorno POS
Como você pode ver, a rotina para encontrar o menor número é chamada ao percorrer o conjunto de dados. Assim que o menor elemento for encontrado, ele é colocado na posição desejada.
como abrir arquivos torrentados mac
Pseudocódigo para classificação por seleção
O pseudocódigo para o algoritmo de ordenação da seleção é fornecido abaixo.
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) Vamos agora ilustrar a classificação de uma matriz usando a classificação por seleção.
Exemplo de classificação de seleção
Considere a seguinte matriz que deve ser classificada como um exemplo de uma classificação de seleção.
qual é o melhor downloader de mp3 grátis
Dada a seguir é uma representação tabular para a ilustração:
Lista não classificada Mínimo elemento Lista ordenada {17,10,7,29,2} dois {} {17,10,7,29} 7 {dois} {17,10,29} 10 {2.7} {17,29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
A partir da ilustração, vemos que a cada passagem, o próximo menor elemento é colocado em sua posição correta na matriz classificada. Em geral, para classificar um array de N elementos, precisamos de N-1 passes no total.
Implementação de classificação de seleção em Java
Vamos agora demonstrar o programa Java para implementar a classificação por seleção.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Resultado:
Matriz original: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Matriz classificada: (2, 5, 7, 10, 15, 20, 23, 34, 42)
No exemplo de java acima, encontramos repetidamente o menor elemento do array e o colocamos no array ordenado até que todo o array esteja completamente classificado.
Seleção Classificar lista vinculada em Java
A seguir, é fornecida uma lista vinculada e temos que classificá-la usando a classificação por seleção. Para fazer isso, usaremos a abordagem recursiva de ordenação por seleção. Em vez de trocar a parte de dados do nó, trocaremos os nós e realinharemos os ponteiros.
Portanto, se a lista vinculada for fornecida da seguinte forma:
A seguir está o programa Java que implementa a classificação acima.
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data Resultado:
Lista original vinculada:
7 9 3 5 1 11
Lista vinculada após classificação:
1 3 5 7 9 11
Observe que no programa acima, realinhamos os links dos nós em vez de classificar apenas o componente de dados do nó.
perguntas frequentes
P # 1) Como funciona a classificação por seleção?
Responda: A classificação por seleção funciona mantendo duas submatrizes. O elemento mínimo da submatriz não classificada é colocado em sua posição adequada em uma submatriz classificada. Então, o segundo elemento mais baixo é colocado em sua posição adequada. Dessa forma, todo o array é classificado selecionando um elemento mínimo durante cada iteração.
Q # 2) Qual é a complexidade do tipo de Seleção?
Responda: A complexidade geral do tipo de seleção é O (ndois), tornando-o o algoritmo ineficiente em conjuntos de dados maiores. Outras técnicas de classificação são mais eficientes.
Q # 3) Quais são as vantagens e desvantagens da classificação por seleção?
Responda: A classificação por seleção é a técnica de classificação local e, portanto, não requer armazenamento adicional para armazenar elementos intermediários.
Ele funciona de forma eficiente em estruturas de dados menores, bem como em conjuntos de dados que estão quase classificados.
A principal desvantagem da técnica de classificação por seleção é que ela tem um desempenho muito ruim à medida que o tamanho da estrutura de dados aumenta. Não só se torna mais lento, mas também diminui a eficiência.
Q # 4) Quantas trocas existem na classificação Seleção?
Responda: A técnica de ordenação por seleção leva o número mínimo de trocas. Para o melhor caso, quando a matriz é classificada, o número de trocas na classificação da seleção é 0.
Q # 5) A classificação por seleção é mais rápida do que a classificação por inserção?
Responda: A classificação por inserção é mais rápida e eficiente, bem como estável. A classificação por seleção é mais rápida apenas para conjuntos de dados menores e estruturas parcialmente classificadas.
Conclusão
A classificação por seleção é uma técnica que funciona selecionando o elemento mínimo ao percorrer a matriz. Para cada passagem / iteração, o próximo elemento mínimo no conjunto de dados é selecionado e colocado em sua posição adequada.
A técnica de ordenação por seleção funciona de maneira eficiente quando o número de elementos no conjunto de dados é menor, mas começa a ter um desempenho insatisfatório conforme o tamanho do conjunto de dados aumenta. Torna-se ineficiente quando comparado a outras técnicas semelhantes, como ordenação por inserção.
Neste tutorial, implementamos exemplos para classificar arrays e listas vinculadas usando classificação por seleção.
=> Visite aqui para ver a série de treinamento Java para todos.
Leitura recomendada
- Como classificar uma matriz em Java - Tutorial com exemplos
- Classificação de seleção em C ++ com exemplos
- Tutorial de comprimento de array Java com exemplos de código
- Método MongoDB Sort () com exemplos
- Jagged Array In Java - Tutorial com exemplos
- Comando de classificação Unix com sintaxe, opções e exemplos
- Reverter uma matriz em Java - 3 métodos com exemplos
- Tutorial JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
