Meni

Sortiranje umetanja u Javi - Algoritam sortiranja umetanja i primjeri

  • Glavni
  • Ostalo
  • Sortiranje umetanja u Javi - Algoritam sortiranja umetanja i primjeri

insertion sort java insertion sort algorithm examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Ovaj vodič objašnjava sortiranje umetanja na Javi, uključujući njegov algoritam, pseudo-kôd i primjere sortiranja nizova, pojedinačno i dvostruko povezan popis:

Tehnika algoritma sortiranja umetanja slična je Bubble sort, ali je malo učinkovitija. Razvrstavanje umetanja izvedivije je i učinkovitije kada je u pitanju mali broj elemenata. Kad je skup podataka veći, trebat će više vremena za sortiranje podataka.

=> Ovdje pogledajte Vodič za početnike za Java.

alati za testiranje mirnih web usluga

Sortiranje umetanja na Javi

Što ćete naučiti:

Uvod u sortiranje umetanja u Javi

U tehnici sortiranja umetanjem pretpostavljamo da je prvi element na popisu već sortiran i započinjemo s drugim elementom. Drugi se element uspoređuje s prvim i zamjenjuje se ako nije u redu. Taj se postupak ponavlja za sve naredne elemente.

Općenito, tehnika umetanja sortiranja uspoređuje svaki element sa svim prethodnim elementima i sortira element tako da ga postavi u odgovarajući položaj.

Kao što je već spomenuto, tehnika sortiranja umetanjem izvedivija je za manji skup podataka, pa se stoga nizovi s malim brojem elemenata mogu sortirati pomoću učinkovite sortiranja umetanjem.

Razvrstavanje umetanja posebno je korisno pri razvrstavanju povezanih struktura podataka popisa. Kao što znate, povezani popisi imaju pokazivače koji upućuju na njegov sljedeći element (pojedinačno povezani popis) i prethodni element (dvostruko povezani popis). To olakšava praćenje prethodnih i sljedećih elemenata.

Stoga je lakše koristiti sortiranje umetanja za sortiranje povezanih popisa. Međutim, sortiranje će potrajati puno vremena ako je podataka više.

U ovom uputstvu razgovarat ćemo o tehnici sortiranja umetanja, uključujući algoritam, pseudo-kôd i primjere. Također ćemo implementirati Java programe za sortiranje niza, pojedinačno povezan popis i dvostruko povezan popis pomoću sortiranja umetanjem.

Algoritam sortiranja umetanja

Algoritam sortiranja umetanja je sljedeći.

Korak 1 : Ponovite korake 2 do 5 za K = 1 do N-1

Korak 2 : postavi temp = A (K)

3. korak : skup J = K - 1

4. korak :

Ponavljajte dok je temp<=A(J)
skup A (J + 1) = A (J)
skup J = J - 1
(kraj unutarnje petlje)

Korak 5 :

postavite A (J + 1) = temp
(kraj petlje)

Korak 6 : Izlaz

Kao što znate, sortiranje umetanja započinje od drugog elementa pod pretpostavkom da je prvi element već sortiran. Gornji koraci ponavljaju se za sve elemente na popisu od drugog elementa nadalje i postavljaju se u željene položaje.

Pseudocode za sortiranje umetanja

Pseudo-kôd za tehniku ​​sortiranja umetanja dan je u nastavku.

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

Dalje, pogledajmo ilustraciju koja prikazuje sortiranje niza pomoću sortiranja umetanjem.

Sortiranje niza pomoću sortiranja umetanja

Uzmimo primjer sortiranja umetanjem pomoću niza.

Niz za sortiranje je sljedeći:

niz koji se sortira

Sada za svaki prolaz uspoređujemo trenutni element sa svim prethodnim elementima. Dakle, u prvom dodavanju započinjemo s drugim elementom.

Usporedite 2. element s 1. elementom

proći 2

proći 3

proći 4

proći 5

proći 6

Dakle, potreban nam je N broj prolaza da bismo u potpunosti sortirali niz koji sadrži N broj elemenata.

c ++ nedefinirana referenca na funkciju u zaglavnoj datoteci

Gornja ilustracija može se sažeti u tabličnom obliku kako je prikazano dolje:

ProćiNesortirani popisusporedbaPoredani popis
jedan{10,2,6,15,4,1}{10,2}{2,10, 6,15,4,1}
dva{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}

Kao što je prikazano na gornjoj ilustraciji, na kraju svakog prolaska jedan element ide na svoje mjesto. Stoga općenito, da bismo postavili N elemenata na njihovo odgovarajuće mjesto, trebaju nam N-1 prolazi.

Implementacija sortiranja umetanja u Javi

Sljedeći program prikazuje implementaciju sortiranja Insertion u Javi. Ovdje imamo niz koji ćemo sortirati pomoću sortiranja 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)); } }

Izlaz:

Izvorni niz: (10, 6, 15, 4, 1, 45)
Sortirani niz: (1, 4, 6, 10, 15, 45)

Provedba sortiranja unosa - izlaz

U gornjoj provedbi vidi se da sortiranje započinje od 2ndelement niza (varijabla petlje j = 1), a zatim se trenutni element uspoređuje sa svim prethodnim elementima. Zatim se element postavlja u pravilan položaj.

Razvrstavanje umetanjem učinkovito djeluje za manje nizove i za nizove koji su djelomično razvrstani tamo gdje je razvrstavanje završeno u manje prolaza.

Sortiranje umetanja stabilna je sorta, tj. Održava redoslijed jednakih elemenata na popisu.

Sortiranje povezanog popisa pomoću sortiranja umetanja

Sljedeći Java program prikazuje sortiranje pojedinačno povezanog popisa pomoću sortiranja 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

Izlaz:

Izvorni povezani popis:
1 8 32 2 10
Poredani povezani popis:
1 2 8 10 32

izlaz - povezani popis

U gore navedenom programu definirali smo klasu koja stvara povezani popis i dodaje mu čvorove te ga sortira. Kako pojedinačno povezani popis ima sljedeći pokazivač, lakše je pratiti čvorove prilikom sortiranja popisa.

Sortiranje dvostruko povezanog popisa pomoću sortiranja umetanja

Sljedeći program sortira dvostruko povezan popis koristeći sortiranje umetanjem. Imajte na umu da, budući da dvostruko povezani popis ima i prethodne i sljedeće pokazivače, pokazivače je lako ažurirati i povezati dok sortirate podatke.

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

Izlaz:

Izvorni dvostruko povezani popis:
1 11 2 7 3 5
Razvrstani dvostruko povezani popis:
1 2 3 5 7 11

Izlaz - dvostruko povezan popis

Često postavljana pitanja

P # 1) Što je sortiranje umetanja u Javi?

Odgovor: Razvrstavanje umetanjem jednostavna je tehnika sortiranja u Javi koja je učinkovita za manji skup podataka i na mjestu. Pretpostavlja se da se prvi element uvijek sortira, a zatim se svaki sljedeći element uspoređuje sa svim svojim prethodnim elementima i postavlja u svoj odgovarajući položaj.

P # 2) Zašto je sortiranje umetanja bolje?

privatni poslužitelji za world of warcraft

Odgovor: Razvrstavanje umetanja brže je za manje skupove podataka kada se druge tehnike poput brzog razvrstavanja dodaju preko rekurzivnih poziva. Razvrstavanje umetanjem relativno je stabilnije od ostalih algoritama za razvrstavanje i zahtijeva manje memorije. Razvrstavanje umetanja također djeluje učinkovitije kada je niz gotovo sortiran.

3. pitanje) Čemu služi sortiranje umetanja?

Odgovor: Razvrstavanje umetanja uglavnom se koristi u računalnim programima koji grade složene programe poput pretraživanja datoteka, pronalaženja puta i kompresije podataka.

P # 4)Koja je učinkovitost sortiranja umetanja?

Odgovor: Razvrstavanje umetanja ima prosječnu izvedbu slučaja od O (n ^ 2). Najbolji slučaj za sortiranje umetanja je kada je niz već sortiran i to je O (n). U najgorem slučaju izvedba sortiranja umetanja opet je O (n ^ 2).

Zaključak

Razvrstavanje umetanjem jednostavna je tehnika sortiranja koja radi na Nizovima ili povezanim popisima. Korisno je kad je skup podataka manji. Kako se skup podataka povećava, ova tehnika postaje sve sporija i neučinkovitija.

Sortiranje umetanja također je stabilnije i stabilnije od ostalih tehnika sortiranja. Ne postoji dodatna memorija jer se zasebna struktura ne koristi za pohranu razvrstanih elemenata.

Razvrstavanje umetanja dobro djeluje na sortiranju povezanih popisa koji su i pojedinačno i dvostruko povezani popisi. To je zato što se povezani popis sastoji od čvorova povezanih pokazivačima. Stoga sortiranje čvorova postaje lakše.

U našem nadolazećem uputstvu razgovarat ćemo o još jednoj tehnici sortiranja u Javi.

=> Pročitajte seriju Easy Java Training.

Preporučena literatura

^