insertion sort java insertion sort algorithm examples
Este tutorial explica a classificação por inserção em Java, incluindo seu algoritmo, pseudocódigo e exemplos de matrizes de classificação, lista vinculada e duplamente vinculada:
A técnica do Algoritmo de classificação por inserção é semelhante à classificação por bolha, mas é um pouco mais eficiente. A classificação por inserção é mais viável e eficaz quando um pequeno número de elementos está envolvido. Quando o conjunto de dados for maior, levará mais tempo para classificar os dados.
=> Dê uma olhada no guia para iniciantes em Java aqui.
como abrir arquivo dat em pdf
O que você aprenderá:
- Introdução à classificação por inserção em Java
- Algoritmo de classificação de inserção
- Pseudocódigo para classificação por inserção
- Classificando uma matriz usando a classificação por inserção
- Implementação de classificação por inserção em Java
- Classificando uma lista vinculada usando a classificação por inserção
- Classificando uma lista duplamente vinculada usando a classificação por inserção
- perguntas frequentes
- Conclusão
Introdução à classificação por inserção em Java
Na técnica de classificação por inserção, assumimos que o primeiro elemento da lista já está classificado e começamos com o segundo elemento. O segundo elemento é comparado com o primeiro e trocado, se não estiver em ordem. Este processo é repetido para todos os elementos subsequentes.
Em geral, a técnica de classificação por inserção compara cada elemento com todos os seus elementos anteriores e classifica o elemento para colocá-lo em sua posição adequada.
Como já mencionado, a técnica de classificação por inserção é mais viável para um conjunto menor de dados e, portanto, matrizes com um pequeno número de elementos podem ser classificados usando a classificação por inserção de forma eficiente.
A classificação por inserção é especialmente útil na classificação de estruturas de dados de listas vinculadas. Como você sabe, as listas vinculadas têm ponteiros que apontam para o próximo elemento (lista vinculada individualmente) e o elemento anterior (lista dupla vinculada). Isso torna mais fácil acompanhar os elementos anteriores e seguintes.
Portanto, é mais fácil usar a classificação por inserção para classificar listas vinculadas. No entanto, a classificação levará muito tempo se os itens de dados forem maiores.
Neste tutorial, discutiremos a técnica de classificação por inserção, incluindo seu algoritmo, pseudocódigo e exemplos. Também implementaremos programas Java para classificar um array, uma lista vinculada individualmente e uma lista duplamente vinculada usando a classificação por inserção.
Algoritmo de classificação de inserção
O algoritmo de classificação por inserção é o seguinte.
Passo 1 : Repita as etapas 2 a 5 para K = 1 a N-1
Passo 2 : definir temp = A [K]
etapa 3 : definir J = K - 1
Passo 4 :
Repita enquanto temp<=A[J]
conjunto A [J + 1] = A [J]
conjunto J = J - 1
[fim do loop interno]
Etapa 5 :
conjunto A [J + 1] = temp
[fim do loop]
Etapa 6 : saída
Como você sabe, a classificação por inserção começa a partir do segundo elemento, supondo que o primeiro elemento já esteja classificado. As etapas acima são repetidas para todos os elementos da lista a partir do segundo elemento e colocados nas posições desejadas.
Pseudocódigo para classificação por inserção
O pseudo-código para a técnica de classificação por inserção é fornecido abaixo.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element while freePosition > 0 and array[freePosition -1] > insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure
A seguir, vamos ver uma ilustração que demonstra a classificação de uma matriz usando a classificação por inserção.
Classificando uma matriz usando a classificação por inserção
Vamos dar um exemplo de classificação por inserção usando um array.
A matriz a ser classificada é a seguinte:
Agora, para cada passagem, comparamos o elemento atual com todos os seus elementos anteriores. Portanto, na primeira passagem, começamos com o segundo elemento.
Portanto, exigimos N número de passagens para classificar completamente uma matriz contendo N número de elementos.
que tipos de e-mails existem
A ilustração acima pode ser resumida em forma de tabela, conforme mostrado abaixo:
Passar | Lista não classificada | comparação | Lista ordenada |
---|---|---|---|
1 | {10,2,6,15,4,1} | {10.2} | {2,10, 6,15,4,1} |
dois | {2,10, 6,15,4,1} | {2,10, 6} | {2,6,10,15,4,1} |
3 | {2,6,10,15,4,1} | {2.6, 10.15} | {2,6,10,15,4,1} |
4 | {2,6,10,15,4,1} | {2.6, 10.15.4} | {2,4,6,10,15,1} |
5 | {2,4,6,10,15,1} | {2,4,6,10,15,1} | {1,2,4,6, 10,15} |
6 | {} | {} | {1,2,4,6, 10,15} |
Conforme mostrado na ilustração acima, ao final de cada passagem, um elemento vai para o seu devido lugar. Portanto, em geral, para colocar N elementos em seus devidos lugares, precisamos de N-1 passes.
Implementação de classificação por inserção em Java
O programa a seguir mostra a implementação da classificação por inserção em Java. Aqui, temos uma matriz a ser classificada usando a classificação de inserção.
import java.util.*; public class Main { public static void main(String[] args) { //declare an array and print the original contents int[] numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray[j]) { numArray[j+1] = numArray[j]; j = j-1; } numArray[j+1] = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } }
Resultado:
Matriz original: [10, 6, 15, 4, 1, 45]
Matriz classificada: [1, 4, 6, 10, 15, 45]
Na implementação acima, é visto que a classificação começa a partir de 2WLelemento do array (variável de loop j = 1) e então o elemento atual é comparado a todos os seus elementos anteriores. O elemento é então colocado em sua posição correta.
A classificação por inserção funciona com eficácia para matrizes menores e para matrizes parcialmente classificadas, onde a classificação é concluída em menos passagens.
A classificação por inserção é uma classificação estável, ou seja, mantém a ordem dos elementos iguais na lista.
Classificando uma lista vinculada usando a classificação por inserção
O programa Java a seguir mostra a classificação de uma lista vinculada individualmente usando a classificação por inserção.
import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val Resultado:
melhor limpeza de disco para windows 10
Lista original vinculada:
1 8 32 2 10
Lista Vinculada Classificada:
1 2 8 10 32
No programa acima, definimos uma classe que cria uma lista vinculada e adiciona nós a ela, bem como a classifica. Como a lista vinculada individualmente possui um próximo ponteiro, é mais fácil manter um registro dos nós ao classificar a lista.
Classificando uma lista duplamente vinculada usando a classificação por inserção
O programa a seguir classifica uma lista duplamente vinculada usando a classificação por inserção. Observe que, como a lista duplamente vinculada possui ponteiros anteriores e posteriores, é fácil atualizar e vincular novamente os ponteiros ao classificar os dados.
class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args[]) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println('
Sorted Doubly Linked List:'); print_DLL(head); } }
Resultado:
Lista duplamente vinculada original:
1 11 2 7 3 5
Lista Duplamente Vinculada Classificada:
1 2 3 5 7 11
perguntas frequentes
P # 1) O que é Insertion Sort em Java?
Responda: A classificação por inserção é uma técnica de classificação simples em Java que é eficiente para um conjunto de dados menor e no local. Supõe-se que o primeiro elemento é sempre classificado e, em seguida, cada elemento subsequente é comparado a todos os seus elementos anteriores e colocado em sua posição adequada.
Q # 2) Por que a classificação por inserção é melhor?
Responda: A classificação por inserção é mais rápida para conjuntos de dados menores quando outras técnicas, como a classificação rápida, adicionam sobrecarga por meio de chamadas recursivas. A classificação por inserção é comparativamente mais estável do que os outros algoritmos de classificação e requer menos memória. A classificação por inserção também funciona com mais eficiência quando a matriz está quase classificada.
Q # 3) Para que é usado o tipo de inserção?
Responda: A classificação por inserção é usada principalmente em aplicativos de computador que criam programas complexos, como pesquisa de arquivos, localização de caminhos e compactação de dados.
Q # 4)Qual é a eficiência da classificação por inserção?
Responda: A classificação por inserção tem um desempenho de caso médio de O (n ^ 2). O melhor caso para classificação por inserção é quando a matriz já está classificada e é O (n). O pior caso de desempenho para classificação por inserção é novamente O (n ^ 2).
Conclusão
A classificação por inserção é uma técnica de classificação simples que funciona em matrizes ou listas vinculadas. É útil quando o conjunto de dados é menor. À medida que o conjunto de dados fica maior, essa técnica se torna mais lenta e ineficiente.
A classificação por inserção também é mais estável e adequada do que as outras técnicas de classificação. Não há sobrecarga de memória, pois nenhuma estrutura separada é usada para armazenar elementos classificados.
A classificação por inserção funciona bem na classificação de listas vinculadas que são listas unidas e duplamente vinculadas. Isso ocorre porque a lista vinculada é composta de nós que são conectados por meio de ponteiros. Portanto, a classificação dos nós se torna mais fácil.
Em nosso próximo tutorial, discutiremos outra técnica de classificação em Java.
=> Leia a série de treinamento Easy Java.
Leitura recomendada
- Classificação de seleção em Java - Algoritmo de classificação de seleção e exemplos
- Classificação de inserção em C ++ com exemplos
- Como classificar uma matriz em Java - Tutorial com exemplos
- Método MongoDB Sort () com exemplos
- Comando de classificação Unix com sintaxe, opções e exemplos
- Classificação Shell em C ++ com exemplos
- Interface Java e tutorial de classe abstrata com exemplos
- Classificação de seleção em C ++ com exemplos