Meni

Razvrstitev vstavitve v Javi - Algoritem razvrščanja vstavkov in primeri

  • Glavni
  • Drugo
  • Razvrstitev vstavitve v Javi - Algoritem razvrščanja vstavkov in primeri

insertion sort java insertion sort algorithm examples

Preizkusite Naš Instrument Za Odpravo Težav

Ta vadnica razlaga sortiranje vstavljanja v Javi, vključno z algoritmom, psevdo-kodo in primeri sortiranja nizov, enojno povezanim in dvojno povezanim seznamom:

Tehnika algoritma za razvrščanje po vstavitvi je podobna Bubble sort, vendar je nekoliko učinkovitejša. Razvrstitev vstavljanja je izvedljivejša in učinkovitejša, če gre za majhno število elementov. Ko je nabor podatkov večji, bo trajalo več časa za razvrščanje podatkov.

=> Tu si oglejte Vodnik za začetnike Java.

kako odpreti datoteko .apk v operacijskem sistemu Windows

Razvrstitev vstavka v Javi

Kaj se boste naučili:

Uvod v razvrščanje vstavkov v Javi

V tehniki razvrščanja vstavljanja predpostavljamo, da je prvi element na seznamu že razvrščen in začnemo z drugim elementom. Drugi element primerjamo s prvim in ga zamenjamo, če ne po vrstnem redu. Ta postopek se ponovi za vse nadaljnje elemente.

Na splošno tehnika vstavljanja razvršča vsak element z vsemi prejšnjimi elementi in razvršča element tako, da ga postavi v pravi položaj.

Kot smo že omenili, je tehnika razvrščanja vstavitve izvedljivejša za manjši nabor podatkov, zato lahko nize z majhnim številom elementov razvrstimo z učinkovitim razvrščanjem vstavitve.

Razvrščanje vstavljanja je še posebej uporabno pri razvrščanju podatkovnih struktur povezanih seznamov. Kot veste, imajo povezani seznami kazalce, ki kažejo na njegov naslednji element (posamezno povezan seznam) in prejšnji element (dvojno povezan seznam). Tako je lažje slediti prejšnjim in naslednjim elementom.

Tako je za razvrščanje povezanih seznamov lažje uporabljati razvrščanje vstavitve. Vendar bo razvrščanje trajalo veliko časa, če je podatkovnih elementov več.

V tej vadnici bomo razpravljali o tehniki razvrščanja vstavkov, vključno z algoritmom, psevdo-kodo in primeri. Izvedli bomo tudi programe Java za razvrščanje matrike, enojno povezanega seznama in dvojno povezanega seznama z razvrstitvijo vstavljanja.

Algoritem razvrščanja vstavkov

Algoritem razvrščanja vstavljanja je naslednji.

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

2. korak : nastavi temp = A (K)

3. korak : nastavite J = K - 1

4. korak :

Ponovite med temp<=A(J)
nastavite A (J + 1) = A (J)
nastavimo J = J - 1
(konec notranje zanke)

5. korak :

nastavite A (J + 1) = temp
(konec zanke)

6. korak : izhod

Kot veste, se vstavljanje razvrsti od drugega elementa ob predpostavki, da je prvi element že razvrščen. Zgornji koraki se ponovijo za vse elemente na seznamu od drugega elementa naprej in jih postavijo v želene položaje.

Psevkodo za razvrstitev vstavljanja

Psevdo-koda za tehniko razvrščanja vstavitve je navedena spodaj.

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

Nato si oglejmo ilustracijo, ki prikazuje razvrščanje matrike z uporabo razvrščanja vstavitve.

Razvrščanje polja z razvrščanjem po vstavljanju

Vzemimo primer razvrščanja vstavljanja z uporabo polja.

Niz, ki ga je treba razvrstiti, je naslednji:

polje, ki ga je treba razvrstiti

Zdaj za vsak prehod primerjamo trenutni element z vsemi prejšnjimi elementi. V prvem podajanju torej začnemo z drugim elementom.

Primerjaj 2. element s 1. elementom

poda 2

poda 3

poda 4

poda 5

podaja 6

Tako za popolno razvrščanje matrike, ki vsebuje N število elementov, potrebujemo N število prehodov.

kako vbrizgati kodo v spletno stran

Zgornjo ponazoritev lahko povzamemo v tabelarni obliki, kot je prikazano spodaj:

MimoNerazvrščen seznamprimerjavaRazvrščen seznam
1.{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}

Kot je prikazano na zgornji sliki, na koncu vsakega prehoda en element gre na svoje mesto. Zato na splošno za postavitev N elementov na njihovo pravilno mesto potrebujemo N-1 prehode.

Izvedba sortiranja vstavkov v Javi

Naslednji program prikazuje izvajanje vrste Insertion v Javi. Tu imamo matriko, ki jo je treba razvrstiti z razvrstitvijo 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)); } }

Izhod:

Izvirno polje: (10, 6, 15, 4, 1, 45)
Razvrščeno polje: (1, 4, 6, 10, 15, 45)

Izvajanje sortiranja vstavljanja - izhod

V zgornji izvedbi je razvidno, da se sortiranje začne od 2ndelement matrike (spremenljivka zanke j = 1), nato pa se trenutni element primerja z vsemi njegovimi prejšnjimi elementi. Nato se element postavi v pravilen položaj.

Razvrščanje z vstavljanjem deluje učinkovito za manjše nize in za nize, ki so delno razvrščeni, če je razvrščanje končano v manj prehodih.

Razvrstitev pri vstavljanju je stabilno razvrščanje, tj. Vzdržuje vrstni red enakih elementov na seznamu.

Razvrščanje povezanega seznama z uporabo razvrstitve vstavljanja

Naslednji program Java prikazuje razvrščanje posamezno povezanega seznama s pomočjo razvrščanja vstavitve.

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

Izhod:

Prvotni povezani seznam:
1 8 32 2 10
Razvrščen povezan seznam:
1 2 8 10 32

izhod - povezan seznam

V zgornjem programu smo definirali razred, ki ustvari povezan seznam in mu doda vozlišča ter ga razvrsti. Ker ima posamezno povezan seznam naslednji kazalec, je lažje slediti vozliščem pri razvrščanju seznama.

Razvrščanje dvojno povezanega seznama z uporabo razvrstitve vstavljanja

Naslednji program razvrsti dvojno povezan seznam z uporabo razvrščanja vstavitve. Ker ima dvojno povezan seznam tako prejšnje kot naslednje kazalce, je med razvrščanjem podatkov kazalce enostavno posodobiti in znova povezati.

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

Izhod:

Originalni dvojno povezan seznam:
1 11 2 7 3 5
Razvrščen dvojno povezan seznam:
1 2 3 5 7 11

Rezultat - dvojno povezan seznam

Pogosto zastavljena vprašanja

V # 1) Kaj je sortiranje vstavljanja v Javi?

Odgovor: Razvrščanje vstavljanja je preprosta tehnika razvrščanja v Javi, ki je učinkovita za manjši nabor podatkov in na mestu. Predpostavlja se, da je prvi element vedno razvrščen, nato pa se vsak naslednji element primerja z vsemi svojimi prejšnjimi elementi in postavi v svoj pravilen položaj.

V # 2) Zakaj je vstavljanje boljše?

Odgovor: Razvrščanje vstavljanja je pri manjših naborih podatkov hitrejše, če druge tehnike, kot je hitro razvrščanje, dodajo režijske stroške z rekurzivnimi klici. Razvrščanje vstavljanja je sorazmerno bolj stabilno kot drugi algoritmi za razvrščanje in zahteva manj pomnilnika. Razvrščanje vstavkov deluje tudi bolj učinkovito, ko je polje skoraj razvrščeno.

3. vprašanje) Za kaj se uporablja vrsta vstavljanja?

Odgovor: Razvrstitev vstavljanja se večinoma uporablja v računalniških aplikacijah, ki gradijo zapletene programe, kot so iskanje datotek, iskanje poti in stiskanje podatkov.

V # 4)Kakšna je učinkovitost sortiranja vstavljanja?

Odgovor: Razvrstitev vstavka ima povprečno uspešnost primera O (n ^ 2). Najboljši primer za razvrščanje vstavljanja je, ko je polje že razvrščeno in je O (n). Najslabše delovanje pri vstavljanju je spet O (n ^ 2).

Zaključek

Razvrščanje vstavljanja je preprosta tehnika razvrščanja, ki deluje na nizih ali povezanih seznamih. Uporabno je, če je nabor podatkov manjši. Ko se nabor podatkov povečuje, postane ta tehnika počasnejša in neučinkovitejša.

testna orodja za upravljanje podatkov odprtokodna

Razvrstitev vstavljanja je tudi bolj stabilna in na mestu kot druge tehnike razvrščanja. Nobenega dodatnega pomnilnika ni, saj se za shranjevanje razvrščenih elementov ne uporablja ločena struktura.

Razvrstitev vstavkov dobro deluje pri razvrščanju povezanih seznamov, ki so enojni in dvojno povezani seznami. To je zato, ker je povezan seznam sestavljen iz vozlišč, ki so povezana s kazalci. Zato je razvrščanje vozlišč lažje.

V naši prihajajoči vadnici bomo razpravljali o še eni tehniki razvrščanja v Javi.

=> Preberite serijo Easy Java Training Series.

Priporočeno branje

^