insertion sort java insertion sort algorithm examples
Denne opplæringen forklarer innsettingssortering i Java, inkludert algoritmen, pseudokoden og eksempler på sorteringsarrayer, enkeltkoblet og dobbeltkoblet liste:
Insertion Sort Algorithm-teknikken ligner Bubble sort, men er litt mer effektiv. Innsettingssortering er mer gjennomførbar og effektiv når et lite antall elementer er involvert. Når datasettet er større, vil det ta mer tid å sortere dataene.
=> Ta en titt på Java Beginners Guide her.
hvordan åpne en apk-fil på android
Hva du vil lære:
Introduksjon til innsettingssortering i Java
I Insertion sort-teknikken antar vi at det første elementet i listen allerede er sortert, og vi begynner med det andre elementet. Det andre elementet sammenlignes med det første og byttes ut hvis ikke i orden. Denne prosessen gjentas for alle påfølgende elementer.
Generelt sammenligner sorteringsteknikken for innsetting hvert element med alle dets tidligere elementer og sorterer elementet for å plassere det i riktig posisjon.
Som allerede nevnt er innsettingstypesorteringsteknikken mer gjennomførbar for et mindre datasett, og dermed kan matriser med et lite antall elementer sorteres ved hjelp av effektiv innsettingssortering.
Sorteringssortering er spesielt nyttig i å sortere datastrukturer for koblede lister. Som du vet har koblede lister pekere som peker til neste element (enkeltkoblet liste) og forrige element (dobbeltkoblet liste). Dette gjør det lettere å holde oversikt over forrige og neste element.
Dermed er det lettere å bruke Insertion sort for å sortere lenker. Sortering vil imidlertid ta mye tid hvis dataelementene er mer.
I denne opplæringen vil vi diskutere Insertion sort-teknikken inkludert dens algoritme, pseudokode og eksempler. Vi vil også implementere Java-programmer for å sortere en matrise, Enkelinket liste og Dobbeltkoblet liste ved hjelp av Insertion sort.
Sorteringsalgoritme
Sorteringsalgoritmen er som følger.
Trinn 1 : Gjenta trinn 2 til 5 for K = 1 til N-1
Steg 2 : sett temp = A (K)
Trinn 3 : sett J = K - 1
Trinn 4 :
Gjenta mens temp<=A(J)
sett A (J + 1) = A (J)
sett J = J - 1
(slutten av indre sløyfe)
Trinn 5 :
sett A (J + 1) = temp
(end of loop)
Trinn 6 : exit
Som du vet starter innsettingssorteringen fra det andre elementet forutsatt at det første elementet allerede er sortert. Ovenstående trinn gjentas for alle elementene i listen fra det andre elementet og utover og settes i ønsket posisjon.
Pseudokode for innsettingssortering
Pseudokoden for teknikken for innsettingssortering er gitt nedenfor.
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 procedureLa oss deretter se en illustrasjon som demonstrerer sortering av en matrise ved hjelp av Insertion sort.
Sortere en serie ved hjelp av innsettingssortering
La oss ta et eksempel på innsettingssortering ved hjelp av en matrise.
Matrisen som skal sorteres er som følger:
Nå for hvert pass, sammenligner vi det nåværende elementet med alle dets tidligere elementer. Så i første omgang starter vi med det andre elementet.
Dermed krever vi N antall passeringer for å fullstendig sortere en matrise som inneholder N antall elementer.
shell scripting intervju spørsmål og svar for erfarne
Illustrasjonen ovenfor kan oppsummeres i tabellform som vist nedenfor:
| Sende | Usortert liste | sammenligning | Sortert liste |
|---|---|---|---|
| 1 | {10,2,6,15,4,1} | {10.2} | {2,10, 6,15,4,1} |
| to | {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} |
Som vist i illustrasjonen ovenfor, på slutten av hvert pass, går ett element på sin rette plass. Derfor trenger vi generelt N-1-passeringer for å plassere N-elementer på riktig sted.
Implementering av innsettingssortering i Java
Følgende program viser implementeringen av Insertion sort i Java. Her har vi en matrise som skal sorteres ved hjelp av Insertion sort.
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)); } } Produksjon:
Original Array: (10, 6, 15, 4, 1, 45)
Sortert matrise: (1, 4, 6, 10, 15, 45)
I implementeringen ovenfor ser vi at sortering begynner fra 2ndelementet i matrisen (loopvariabel j = 1) og deretter blir det nåværende elementet sammenlignet med alle de tidligere elementene. Elementet plasseres deretter i riktig posisjon.
Innsettingssortering fungerer effektivt for mindre matriser og for matriser som er delvis sortert der sorteringen er fullført i færre passeringer.
Innsettingssortering er en stabil sortering, dvs. at den opprettholder rekkefølgen på like elementer i listen.
Sortere en koblet liste ved hjelp av innsettingssortering
Det følgende Java-programmet viser sorteringen av en enkeltkoblet liste ved hjelp av Insertion-sorteringen.
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 Produksjon:
Opprinnelig koblet liste:
1 8 32 2 10
Sortert koblet liste:
1 2 8 10 32
I det ovennevnte programmet har vi definert en klasse som oppretter en koblet liste og legger til noder i den samt sorterer den. Ettersom den enkeltkoblede listen har en neste peker, er det lettere å holde oversikt over noder når du sorterer listen.
Sortere en dobbeltkoblet liste ved hjelp av innsettingssortering
Følgende program sorterer en dobbeltkoblet liste ved hjelp av Insertion sort. Merk at siden den dobbeltkoblede listen har både forrige og neste pekepinn, er det enkelt å oppdatere og koble pekepinnene til mens du sorterer dataene.
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); } } Produksjon:
Opprinnelig dobbeltkoblet liste:
1 11 2 7 3 5
Sortert dobbeltkoblet liste:
1 2 3 5 7 11
ofte stilte spørsmål
Q # 1) Hva er innsettingssortering i Java?
topp 10 rekrutteringsbyråer i verden
Svar: Innsettingssortering er en enkel sorteringsteknikk i Java som er effektiv for et mindre datasett og på plass. Det antas at det første elementet alltid er sortert, og deretter sammenlignes hvert påfølgende element med alle dets tidligere elementer og plasseres i riktig posisjon.
Q # 2) Hvorfor er innsetting bedre?
Svar: Innsettingssortering er raskere for mindre datasett når de andre teknikkene som rask sortering legger til overhead gjennom rekursive samtaler. Innsettingssortering er relativt mer stabil enn de andre sorteringsalgoritmene og krever mindre minne. Innsettingssortering fungerer også mer effektivt når matrisen nesten er sortert.
Q # 3) Hva brukes innsettingssorten til?
Svar: Sorteringssortering brukes hovedsakelig i dataprogrammer som bygger komplekse programmer som filsøk, banesøk og datakomprimering.
Q # 4)Hva er effektiviteten til innsettingssortering?
Svar: Innsettingssortering har en gjennomsnittlig caseytelse på O (n ^ 2). Det beste tilfellet for sortering av innsetting er når matrisen allerede er sortert og den er O (n). Verste tilfelle for innsetting er igjen O (n ^ 2).
Konklusjon
Innsettingssortering er en enkel sorteringsteknikk som fungerer på Arrays eller koblede lister. Det er nyttig når datasettet er mindre. Når datasettet blir større, blir denne teknikken tregere og ineffektiv.
Innsettingssorteringen er også mer stabil og på plass enn de andre sorteringsteknikkene. Det er ikke noe minneoverhead da ingen egen struktur brukes til å lagre sorterte elementer.
Innsettingssortering fungerer bra på å sortere sammenkoblede lister som både er enkeltstående og dobbeltkoblede lister. Dette er fordi den koblede listen består av noder som er koblet til via pekere. Derfor blir sortering av noder lettere.
I vår kommende opplæring vil vi diskutere enda en sorteringsteknikk i Java.
=> Les gjennom Easy Java Training Series.
Anbefalt lesing
- Valgsortering i Java - Valgsorteringsalgoritme og eksempler
- Innsettingssortering i C ++ med eksempler
- Hvordan sortere en matrise i Java - Veiledning med eksempler
- MongoDB Sort () Metode med eksempler
- Unix sorteringskommando med syntaks, alternativer og eksempler
- Skalsortering i C ++ med eksempler
- Java-grensesnitt og abstrakt klasseopplæring med eksempler
- Utvalgssortering i C ++ med eksempler
