Meniu

Sortare prin inserare în Java - Algoritm de sortare și exemple

  • Principal
  • Alte
  • Sortare prin inserare în Java - Algoritm de sortare și exemple

insertion sort java insertion sort algorithm examples

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Acest tutorial explică sortarea prin inserție în Java, inclusiv algoritmul, pseudocodul și exemple de sortare a matricelor, listă legată individual și listă legată dublu:

Tehnica Algoritmului de sortare a inserției este similară cu sortarea cu bule, dar este puțin mai eficientă. Sortarea prin inserție este mai fezabilă și mai eficientă atunci când este implicat un număr mic de elemente. Când setul de date este mai mare, va dura mai mult timp pentru a sorta datele.

=> Consultați aici Ghidul pentru începători Java.

aplicații pentru a descărca videoclipuri de pe YouTube

Inserare Sortare în Java

Ce veți învăța:

Introducere în sortare prin inserție în Java

În tehnica de sortare prin inserție, presupunem că primul element din listă este deja sortat și începem cu al doilea element. Al doilea element este comparat cu primul și schimbat dacă nu în ordine. Acest proces se repetă pentru toate elementele ulterioare.

În general, tehnica de sortare prin inserție compară fiecare element cu toate elementele sale anterioare și sortează elementul pentru ao plasa în poziția corectă.

După cum sa menționat deja, tehnica de sortare prin inserție este mai fezabilă pentru un set mai mic de date și, astfel, matricile cu un număr mic de elemente pot fi sortate folosind eficient sortarea prin inserție.

Sortarea prin inserție este utilă în special în sortarea structurilor de date ale listelor legate. După cum știți, listele legate au indicii care indică elementul următor (lista legată individual) și elementul anterior (lista dublă legată). Acest lucru facilitează urmărirea elementelor anterioare și următoare.

Astfel, este mai ușor să utilizați sortarea prin inserție pentru sortarea listelor legate. Cu toate acestea, sortarea va dura mult timp dacă elementele de date sunt mai multe.

În acest tutorial, vom discuta despre tehnica de sortare Insertion, inclusiv algoritmul, pseudo-codul și exemplele sale. De asemenea, vom implementa programe Java pentru a sorta o matrice, o listă legată individual și o listă legată dublu folosind sortarea prin inserție.

Algoritm de sortare a inserției

Algoritmul de sortare a inserției este după cum urmează.

Pasul 1 : Repetați pașii de la 2 la 5 pentru K = 1 la N-1

Pasul 2 : set temp = A (K)

Pasul 3 : set J = K - 1

Pasul 4 :

Repetați în timp ce temp<=A(J)
set A (J + 1) = A (J)
setul J = J - 1
(sfârșitul buclei interioare)

Pasul 5 :

set A (J + 1) = temp
(sfârșitul buclei)

Pasul 6 : Ieșire

După cum știți, sortarea inserției începe de la al doilea element presupunând că primul element este deja sortat. Pașii de mai sus se repetă pentru toate elementele din listă începând cu al doilea element și se pun în pozițiile lor dorite.

Pseudocod pentru sortare prin inserție

Pseudo-codul pentru tehnica de sortare a inserției este dat mai jos.

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

În continuare, să vedem o ilustrație care demonstrează sortarea unui tablou folosind sortarea prin inserție.

Sortarea unui tablou utilizând sortarea prin inserție

Să luăm un exemplu de sortare prin inserție folosind o matrice.

Matricea care trebuie sortată este după cum urmează:

matrice de sortat

Acum, pentru fiecare trecere, comparăm elementul curent cu toate elementele sale anterioare. Deci, în prima trecere, începem cu al doilea element.

Comparați al doilea element cu primul element

trece 2

treceți 3

treceți 4

treceți 5

treceți 6

Astfel, avem nevoie de N număr de treceri pentru a sorta complet o matrice care conține N număr de elemente.

cel mai bun software de monitorizare CPU și GPU

Ilustrația de mai sus poate fi rezumată sub formă de tabel, după cum se arată mai jos:

TreceListă nesortatăcomparaţieListă sortată
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
Două{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}

După cum se arată în ilustrația de mai sus, la sfârșitul fiecărei treceri, un element merge în locul său corespunzător. Prin urmare, în general, pentru a plasa N elemente în locul lor adecvat, avem nevoie de N-1 trece.

Implementare sortare inserție în Java

Următorul program arată implementarea sortării Insertion în Java. Aici avem o matrice care trebuie sortată folosind sortarea Insertion.

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

Ieșire:

Matrice originală: (10, 6, 15, 4, 1, 45)
Matrice sortate: (1, 4, 6, 10, 15, 45)

Implementarea sortării prin inserție - ieșire

În implementarea de mai sus, se vede că sortarea începe din 2ndelement al matricei (variabila buclă j = 1) și apoi elementul curent este comparat cu toate elementele sale anterioare. Elementul este apoi plasat în poziția corectă.

Sortarea prin inserție funcționează eficient pentru tablourile mai mici și pentru tablourile care sunt parțial sortate acolo unde sortarea este finalizată în mai puține treceri.

Sortarea prin inserție este o sortare stabilă, adică menține ordinea elementelor egale din listă.

Sortarea unei liste legate folosind sortarea prin inserare

Următorul program Java arată sortarea unei liste legate individual folosind sortarea Insertion.

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

Ieșire:

Lista originală legată:
1 8 32 2 10
Listă legată sortată:
1 2 8 10 32

ieșire - Listă legată

În programul de mai sus, am definit o clasă care creează o listă legată și îi adaugă noduri și o sortează. Deoarece lista legată individual are următorul indicator, este mai ușor să țineți o evidență a nodurilor atunci când sortați lista.

Sortarea unei liste cu legături duble folosind sortarea prin inserare

Următorul program sortează o listă dublă legată folosind sortarea prin inserare. Rețineți că, întrucât lista dublă legată are atât indicatori anteriori, cât și indicatori următori, este ușor să actualizați și să reconectați indicatorii în timp ce sortați datele.

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

Ieșire:

Lista originală dublă legată:
1 11 2 7 3 5
Lista sortată dublă legată:
1 2 3 5 7 11

Ieșire - Listă legată dublu

întrebări frecvente

Q # 1) Ce este Sortarea prin inserție în Java?

Răspuns: Sortarea prin inserție este o tehnică simplă de sortare în Java, care este eficientă pentru un set de date mai mic și la locul său. Se presupune că primul element este întotdeauna sortat și apoi fiecare element ulterior este comparat cu toate elementele sale anterioare și plasat în poziția sa corectă.

Q # 2) De ce este mai bun Insertion Sort?

Răspuns: Sortarea prin inserție este mai rapidă pentru seturile de date mai mici, atunci când celelalte tehnici, cum ar fi sortarea rapidă, adaugă overhead prin apeluri recursive. Sortarea prin inserție este comparativ mai stabilă decât ceilalți algoritmi de sortare și necesită mai puțină memorie. Sortarea prin inserție funcționează și mai eficient atunci când tabloul este aproape sortat.

Q # 3) La ce se folosește Sortarea prin inserție?

Răspuns: Sortarea prin inserție este utilizată mai ales în aplicații informatice care construiesc programe complexe, cum ar fi căutarea fișierelor, căutarea căilor și compresia datelor.

Q # 4)Care este eficiența sortării prin inserție?

Răspuns: Sortarea prin inserție are o performanță medie a cazului O (n ^ 2). Cel mai bun caz pentru sortarea inserției este atunci când matricea este deja sortată și este O (n). Performanța în cel mai rău caz pentru sortarea inserției este din nou O (n ^ 2).

Concluzie

Sortarea prin inserție este o tehnică simplă de sortare care funcționează pe tablouri sau liste legate. Este util atunci când setul de date este mai mic. Pe măsură ce setul de date crește, această tehnică devine mai lentă și ineficientă.

cel mai bun mod de a curăța Windows 10 de registry

Sortarea prin inserție este, de asemenea, mai stabilă și la locul său decât celelalte tehnici de sortare. Nu există cheltuieli de memorie, deoarece nu este utilizată o structură separată pentru stocarea elementelor sortate.

Sortarea prin inserție funcționează bine la sortarea listelor conectate care sunt atât liste individuale, cât și liste dublă. Acest lucru se datorează faptului că lista legată este alcătuită din noduri care sunt conectate prin pointeri. Prin urmare, sortarea nodurilor devine mai ușoară.

În viitorul nostru tutorial, vom discuta încă o altă tehnică de sortare în Java.

=> Citiți seria Easy Training Java.

Lectură recomandată

^