Menú

Classificació per inserció a Java: algorisme i exemples d'ordenació per inserció

  • Principal
  • Altres
  • Classificació per inserció a Java: algorisme i exemples d'ordenació per inserció

insertion sort java insertion sort algorithm examples

Proveu El Nostre Instrument Per Eliminar Problemes

Aquest tutorial explica la classificació per inserció a Java, incloent-hi l'algorisme, el pseudocodi i exemples d'ordenació de matrius, llista enllaçada individualment i lligada doblement enllaçada:

La tècnica de l’algoritme d’ordenació per inserció és similar a la classificació Bubble, però és una mica més eficient. L’ordenació per inserció és més factible i eficaç quan es tracta d’un nombre reduït d’elements. Quan el conjunt de dades sigui més gran, trigarà més temps a ordenar-les.

=> Feu una ullada a la guia per a principiants de Java aquí

sql plsql preguntes i respostes de l'entrevista

Classificació per inserció a Java

Què aprendreu:

Introducció a la classificació per inserció a Java

A la tècnica d'ordenació per inserció, suposem que el primer element de la llista ja està ordenat i comencem pel segon element. El segon element es compara amb el primer i es canvia si no en ordre. Aquest procés es repeteix per a tots els elements posteriors.

En general, la tècnica d’ordenació per inserció compara cada element amb tots els elements anteriors i ordena l’element per situar-lo a la seva posició adequada.

Com ja s'ha esmentat, la tècnica d'ordenació per inserció és més factible per a un conjunt de dades més petit i, per tant, es poden ordenar matrius amb un nombre reduït d'elements mitjançant l'ordenació per inserció.

L’ordenació per inserció és especialment útil per ordenar estructures de dades de llistes enllaçades. Com ja sabeu, les llistes enllaçades tenen indicadors que apunten al seu següent element (llista enllaçada individualment) i a l’element anterior (llista enllaçada doble). Això fa que sigui més fàcil fer un seguiment dels elements anteriors i següents.

Per tant, és més fàcil utilitzar el tipus d'inserció per ordenar llistes enllaçades. Tanmateix, l’ordenació trigarà molt de temps si els elements de dades són més.

En aquest tutorial, parlarem de la tècnica d'ordenació d'inserció que inclou el seu algorisme, pseudocodi i exemples. També implementarem programes Java per ordenar una matriu, una llista enllaçada individualment i una llista doblement enllaçada mitjançant la classificació per inserció.

Algorisme d'ordenació per inserció

L’algorisme d’ordenació per inserció és el següent.

Pas 1 : Repetiu els passos 2 a 5 per K = 1 a N-1

Pas 2 : set temp = A (K)

Pas 3 : conjunt J = K - 1

Pas 4 :

Repetiu mentre estigui la temp<=A(J)
conjunt A (J + 1) = A (J)
conjunt J = J - 1
(final del bucle intern)

Pas 5 :

conjunt A (J + 1) = temp
(final del bucle)

Pas 6 : sortir

Com ja sabeu, l’ordenació per inserció comença a partir del segon element suposant que el primer element ja està ordenat. Els passos anteriors es repeteixen per a tots els elements de la llista a partir del segon element i es posen a les posicions desitjades.

Pseudocodi per ordenar per inserció

A continuació es dóna el pseudocodi per a la tècnica d’ordenació per inserció.

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 continuació, vegem una il·lustració que demostra ordenar una matriu mitjançant la classificació per inserció.

Ordenació d 'una matriu mitjançant la classificació per inserció

Prenguem un exemple d'ordenació per inserció mitjançant una matriu.

La matriu que cal ordenar és la següent:

matriu per ordenar

Ara, per a cada passada, comparem l’element actual amb tots els seus elements anteriors. Així doncs, a la primera passada, comencem pel segon element.

Compareu el segon element amb el primer element

passada 2

passada 3

passar 4

passar 5

passar 6

Per tant, necessitem N nombre de passades per ordenar completament una matriu que contingui N nombre d'elements.

millor netejador d'ordinadors gratuït per a Windows 10

La il·lustració anterior es pot resumir en forma de taula com es mostra a continuació:

PassarLlista no classificadacomparacióLlista ordenada
1{10,2,6,15,4,1}{10,2}{2,10, 6,15,4,1}
2{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}

Com es mostra a la il·lustració anterior, al final de cada passada, un element va al seu lloc adequat. Per tant, en general, per col·locar N elements al seu lloc adequat, necessitem passos N-1.

Implementació d'ordenació d'inserció a Java

El programa següent mostra la implementació del tipus d'inserció a Java. Aquí tenim una matriu per ordenar-la mitjançant la classificació per inserció.

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)); } }

Sortida:

Matriu original: (10, 6, 15, 4, 1, 45)
Matriu ordenada: (1, 4, 6, 10, 15, 45)

Implementació de la inserció Sort - Sort

A la implementació anterior, es veu que l’ordenació comença a partir de la 2ndelement de la matriu (variable de bucle j = 1) i llavors l'element actual es compara amb tots els seus elements anteriors. L'element es col·loca a la seva posició correcta.

La classificació per inserció funciona de manera eficaç per a matrius més petits i per a matrius que s’ordenen parcialment quan l’ordenació es completa en menys passades.

L’ordenació per inserció és un tipus estable, és a dir, manté l’ordre d’elements iguals a la llista.

Ordenació d'una llista enllaçada mitjançant l'ordenació per inserció

El següent programa Java mostra l’ordenació d’una llista enllaçada individualment mitjançant l’ordenació per inserció.

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

Sortida:

Llista enllaçada original:
1 8 32 2 10
Llista enllaçada ordenada:
1 2 8 10 32

sortida - Llista enllaçada

Al programa anterior, hem definit una classe que crea una llista enllaçada i hi afegeix nodes, a més d'ordenar-la. Com que la llista enllaçada individualment té un següent punter, és més fàcil fer un seguiment dels nodes a l'hora d'ordenar la llista.

Ordenació d’una llista doblement enllaçada mitjançant la classificació per inserció

El programa següent ordena una llista doblement enllaçada mitjançant la classificació per inserció. Tingueu en compte que, com que la llista doblement enllaçada té indicadors anteriors i següents, és fàcil actualitzar i enllaçar els indicadors mentre s’ordenen les dades.

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); } }

Sortida:

Llista original doblement enllaçada:
1 11 2 7 3 5
Llista ordenada doblement enllaçada:
1 2 3 5 11 jul

Sortida: llista doblement enllaçada

Preguntes freqüents

P # 1) Què és la classificació per inserció a Java?

Resposta: L’ordenació per inserció és una tècnica d’ordenació simple a Java que és eficient per a un conjunt de dades més petit i al seu lloc. Se suposa que el primer element sempre està ordenat i, a continuació, cada element posterior es compara amb tots els elements anteriors i es col·loca a la seva posició adequada.

Q # 2) Per què és millor la inserció?

Resposta: L’ordenació per inserció és més ràpida per a conjunts de dades més petits quan la resta de tècniques, com l’ordenació ràpida, afegeixen despeses generals mitjançant trucades recursives. L’ordenació per inserció és comparativament més estable que la resta d’algoritmes d’ordenació i requereix menys memòria. La classificació per inserció també funciona de manera més eficient quan la matriu està gairebé ordenada.

Q # 3) Per a què s'utilitza la Classificació d'inserció?

Resposta: L’ordenació per inserció s’utilitza principalment en aplicacions informàtiques que creen programes complexos com la cerca de fitxers, la cerca de camins i la compressió de dades.

Q # 4)Quina és l’eficiència de la classificació per inserció?

Resposta: La classificació per inserció té un rendiment mitjà de majúscules i minúscules d’O (n ^ 2). El millor cas per ordenar la inserció és quan la matriu ja està ordenada i és O (n). El rendiment del pitjor dels casos per a la classificació per inserció torna a ser O (n ^ 2).

Conclusió

L’ordenació per inserció és una tècnica d’ordenació senzilla que funciona en matrius o llistes enllaçades. És útil quan el conjunt de dades és més petit. A mesura que el conjunt de dades es fa més gran, aquesta tècnica es torna més lenta i ineficient.

El tipus d'inserció també és més estable i al lloc que les altres tècniques d'ordenació. No hi ha cap sobrecàrrega de memòria, ja que no s’utilitza cap estructura separada per emmagatzemar elements ordenats.

L’ordenació per inserció funciona bé en l’ordenació de llistes enllaçades que són llistes enllaçades individualment i doblement. Això es deu al fet que la llista enllaçada està formada per nodes connectats mitjançant punteres. Per tant, l’ordenació de nodes es fa més fàcil.

preguntes i respostes de l'entrevista de proves de programari per a experimentats

Al nostre proper tutorial, parlarem d’una altra tècnica d’ordenació a Java.

=> Llegiu la sèrie de formació Java fàcil.

Lectura recomanada

^