Menu

Insertion Sort In Java - Insertion Sort Algorithm & Eksempler

  • Vigtigste
  • Andet
  • Insertion Sort In Java - Insertion Sort Algorithm & Eksempler

insertion sort java insertion sort algorithm examples

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning forklarer indsættelsessortering i Java, herunder algoritmen, pseudokoden og eksempler på sorteringsarrays, enkeltkoblet og dobbeltkoblet liste:

Insertion Sort Algorithm-teknikken svarer til Bubblesortering, men er lidt mere effektiv. Indsætningssortering er mere gennemførlig og effektiv, når et lille antal elementer er involveret. Når datasættet er større, tager det mere tid at sortere dataene.

=> Se på Java Beginners Guide her.

bedste software til oprydning af pc

Indsættelse Sorter i Java

Hvad du vil lære:

Introduktion til indsætningssortering i Java

I Insertion sort-teknikken antager vi, at det første element på listen allerede er sorteret, og vi begynder med det andet element. Det andet element sammenlignes med det første og byttes, hvis det ikke er i rækkefølge. Denne proces gentages for alle de efterfølgende elementer.

Generelt sammenligner Insertion-sorteringsteknikken hvert element med alle dets tidligere elementer og sorterer elementet for at placere det i sin rette position.

Som allerede nævnt er Insertion-sorteringsteknikken mere gennemførlig for et mindre datasæt, og arrays med et lille antal elementer kan således sorteres ved hjælp af effektiv Insertion-sortering.

Indsorteringssortering er især nyttig ved sortering af sammenkædede listedatastrukturer. Som du ved, har sammenkædede lister henvisninger, der peger på det næste element (enkeltkædet liste) og det forrige element (dobbeltkædet liste). Dette gør det lettere at holde styr på de forrige og næste elementer.

Således er det lettere at bruge indsættelsessortering til sortering af sammenkædede lister. Men sortering vil tage meget tid, hvis dataelementerne er mere.

I denne vejledning vil vi diskutere Insertion-sorteringsteknikken inklusive dens algoritme, pseudokode og eksempler. Vi implementerer også Java-programmer til at sortere en matrix, enkeltkædet liste og dobbeltkædet liste ved hjælp af indsættelsessortering.

Sorteringsalgoritme

Sorteringsalgoritmen er som følger.

Trin 1 : Gentag trin 2 til 5 for K = 1 til N-1

Trin 2 : indstil temp = A (K)

Trin 3 : indstil J = K - 1

Trin 4 :

Gentag mens temp<=A(J)
sæt A (J + 1) = A (J)
indstil J = J - 1
(slutning af indre sløjfe)

Trin 5 :

indstil A (J + 1) = temp
(slutningen af ​​løkken)

Trin 6 : Afslut

Som du ved, starter indsættelsessortering fra det andet element forudsat at det første element allerede er sorteret. Ovenstående trin gentages for alle elementerne på listen fra det andet element og fremefter og placeres i deres ønskede positioner.

Pseudokode til sortering af indsættelse

Pseudokoden til indsættelsessorteringsteknikken er angivet 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 procedure

Lad os derefter se en illustration, der viser sortering af et array ved hjælp af Insertion sort.

Sortering af en matrix ved hjælp af indsættelsessortering

Lad os tage et eksempel på indsættelsessortering ved hjælp af en matrix.

Det array, der skal sorteres, er som følger:

array, der skal sorteres

Nu for hvert pas sammenligner vi det aktuelle element med alle dets tidligere elementer. Så i første omgang starter vi med det andet element.

Sammenlign 2. element med 1. element

bestå 2

bestå 3

bestå 4

bestå 5

bestå 6

Således kræver vi N antal gennemløb for fuldstændigt at sortere en matrix, der indeholder N antal elementer.

unix finde forskel mellem to filer

Ovenstående illustration kan opsummeres i tabelform som vist nedenfor:

PassereUsorteret listesammenligningSorteret 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 illustrationen ovenfor, i slutningen af ​​hvert pass, går et element på sin rette plads. Derfor har vi generelt brug for N-1-passeringer for at placere N-elementer på deres rette sted.

Implementering af indsætningssortering i Java

Følgende program viser implementeringen af ​​indsættelsessorteringen i Java. Her har vi et array, der skal sorteres ved hjælp af Insertion-sorteringen.

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

Produktion:

Original Array: (10, 6, 15, 4, 1, 45)
Sorteret matrix: (1, 4, 6, 10, 15, 45)

Implementering af indsættelsessortering - output

I ovenstående implementering ses det, at sortering begynder fra 2ndelement i arrayet (loop variabel j = 1) og derefter sammenlignes det aktuelle element med alle dets tidligere elementer. Elementet placeres derefter i sin korrekte position.

Indsorteringssortering fungerer effektivt for mindre arrays og for arrays, der delvist sorteres, hvor sorteringen er afsluttet med færre passeringer.

Indsorteringssortering er en stabil sortering, dvs. den opretholder rækkefølgen af ​​lige elementer på listen.

Sortering af en sammenkædet liste ved hjælp af indsættelsessortering

Følgende Java-program viser sorteringen af ​​en enkelt linket liste ved hjælp af indsættelsessorteringen.

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

Produktion:

Oprindelig sammenkædet liste:
1 8 32 2 10
Sorteret sammenkædet liste:
1 2 8 10 32

output - Tilknyttet liste

I ovenstående program har vi defineret en klasse, der opretter en linket liste og tilføjer noder til den såvel som sorterer den. Da den enkeltlinkede liste har en næste markør, er det lettere at holde styr på noder, når du sorterer listen.

Sortering af en dobbeltkoblet liste ved hjælp af indsættelsessortering

Det følgende program sorterer en dobbeltkoblet liste ved hjælp af Insertion sort. Bemærk, at da den dobbeltkoblede liste har både forrige og næste markør, er det let at opdatere og linke markørerne igen, 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); } }

Produktion:

Oprindeligt dobbeltkoblet liste:
1 11 2 7 3 5
Sorteret dobbeltkoblet liste:
1 2 3 5 7 11

Output - Dobbeltkoblet liste

Ofte stillede spørgsmål

Q # 1) Hvad er indsættelsessortering i Java?

Svar: Indsorteringssortering er en simpel sorteringsteknik i Java, der er effektiv til et mindre datasæt og på plads. Det antages, at det første element altid sorteres, og at hvert efterfølgende element sammenlignes med alle dets tidligere elementer og placeres i sin rette position.

Q # 2) Hvorfor er indsættelsessortering bedre?

Svar: Indsættelsessortering er hurtigere for mindre datasæt, når de andre teknikker som hurtig sortering tilføjer overhead gennem rekursive opkald. Indsorteringssortering er forholdsvis mere stabil end de andre sorteringsalgoritmer og kræver mindre hukommelse. Insertion sort fungerer også mere effektivt, når arrayet næsten er sorteret.

Q # 3) Hvad bruges indsættelsessorteringen til?

Svar: Indsorteringssorter bruges mest i computerapplikationer, der bygger komplekse programmer som filsøgning, stedsøgning og datakomprimering.

Q # 4)Hvad er effektiviteten ved indsættelsessortering?

Svar: Indsættelsessortering har en gennemsnitlig case-ydeevne på O (n ^ 2). Det bedste tilfælde for sortering af indsættelse er, når arrayet allerede er sorteret, og det er O (n). Worst-case ydeevne for indsættelse er igen O (n ^ 2).

Konklusion

Indsorteringssortering er en simpel sorteringsteknik, der fungerer på Arrays eller sammenkædede lister. Det er nyttigt, når datasættet er mindre. Efterhånden som datasættet bliver større, bliver denne teknik langsommere og ineffektiv.

Insertion-sorteringen er også mere stabil og på stedet end de andre sorteringsteknikker. Der er ingen hukommelsesoverhead, da der ikke bruges nogen separat struktur til lagring af sorterede elementer.

Indsætningssortering fungerer godt ved sortering af sammenkædede lister, der er både enkeltstående og dobbeltkædede lister. Dette skyldes, at den sammenkædede liste består af noder, der er forbundet via markører. Derfor bliver sortering af noder lettere.

hvordan man åbner en apk-fil

I vores kommende tutorial vil vi diskutere endnu en sorteringsteknik i Java.

=> Læs gennem Easy Java Training Series.

Anbefalet læsning

^