Meny

Insertion Sort In Java - Insertion Sort Algorithm & Exempel

  • Huvud
  • Övrig
  • Insertion Sort In Java - Insertion Sort Algorithm & Exempel

insertion sort java insertion sort algorithm examples

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning förklarar insättningssortering i Java inklusive dess algoritm, pseudokod och exempel på sorteringsarrayer, singelinkad och dubbelt länkad lista:

Insertion Sort Algorithm-tekniken liknar Bubble sort men är lite effektivare. Insättningssortering är mer genomförbar och effektiv när ett litet antal element är inblandade. När datamängden är större tar det mer tid att sortera data.

=> Ta en titt på Java-nybörjarguiden här.

databas användargränssnitt och programvara för frågan

Insättningssortering i Java

Vad du kommer att lära dig:

Introduktion till insättningssortering i Java

I insättningssorteringstekniken antar vi att det första elementet i listan redan är sorterat och vi börjar med det andra elementet. Det andra elementet jämförs med det första och byts om inte i ordning. Denna process upprepas för alla efterföljande element.

Generellt jämför Intextsorteringstekniken varje element med alla dess tidigare element och sorterar elementet för att placera det i rätt läge.

Som redan nämnts är insättningssorteringstekniken mer genomförbar för en mindre uppsättning data, och därmed kan matriser med ett litet antal element sorteras med effektiv insättningssortering.

Insättningssortering är särskilt användbar vid sortering av länkade datastrukturer. Som du vet har länkade listor pekare som pekar på nästa element (enstaka länkad lista) och föregående element (dubbellänkad lista). Detta gör det lättare att hålla reda på föregående och nästa element.

Således är det lättare att använda insättningssortering för att sortera länkade listor. Sortering tar dock mycket tid om dataobjekten är fler.

I den här handledningen kommer vi att diskutera insättningssorteringstekniken inklusive dess algoritm, pseudokod och exempel. Vi kommer också att implementera Java-program för att sortera en matris, singellänkad lista och dubbelt länkad lista med hjälp av insättningssortering.

Sorteringsalgoritm

Insättningssorteringsalgoritmen är som följer.

Steg 1 : Upprepa steg 2 till 5 för K = 1 till N-1

Steg 2 : ställa in temp = A (K)

Steg 3 : ställ in J = K - 1

Steg 4 :

Upprepa medan temp<=A(J)
ställa in (J + 1) = A (J)
ställ in J = J - 1
(slutet av den inre slingan)

Steg 5 :

ställ in A (J + 1) = temp
(slutet av slingan)

Steg 6 : utgång

Som du vet börjar insättningssortering från det andra elementet förutsatt att det första elementet redan är sorterat. Ovanstående steg upprepas för alla element i listan från det andra elementet och framåt och placeras i önskade positioner.

Pseudokod för insättningssortering

Pseudokoden för insättningssorteringstekniken ges nedan.

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

Låt oss sedan se en illustration som visar att man sorterar en matris med hjälp av Insertion sort.

Sortera en matris med hjälp av insättningssortering

Låt oss ta ett exempel på insättningssortering med hjälp av en matris.

Matrisen som ska sorteras är som följer:

array som ska sorteras

Nu för varje pass jämför vi det aktuella elementet med alla dess tidigare element. Så i det första passet börjar vi med det andra elementet.

Jämför det andra elementet med det första elementet

pass 2

pass 3

pass 4

passera 5

pass 6

Således kräver vi N antal passeringar för att helt sortera en matris som innehåller N antal element.

shell scripting intervju frågor och svar för erfarna

Ovanstående illustration kan sammanfattas i tabellform enligt nedan:

PasseraOsorterad listajämförelseSorterad lista
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
två{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 visas i illustrationen ovan, i slutet av varje pass, går ett element på rätt plats. För att placera N-element på sin rätta plats behöver vi därför N-1-pass.

Insättningssorteringsimplementering i Java

Följande program visar implementeringen av insättningssorteringen i Java. Här har vi en matris som ska sorteras med insättningssorteringen.

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:

Originalmatris: (10, 6, 15, 4, 1, 45)
Sorterad matris: (1, 4, 6, 10, 15, 45)

Implementering av insättningssortering - utdata

I ovanstående implementering ser man att sortering börjar från 2ndelement i matrisen (loopvariabel j = 1) och sedan jämförs det aktuella elementet med alla dess tidigare element. Elementet placeras sedan i rätt läge.

Insättningssortering fungerar effektivt för mindre matriser och för matriser som delvis sorteras där sorteringen slutförs med färre pass.

Insättningssortering är en stabil sortering, d.v.s. den håller ordningen på lika element i listan.

Sortera en länkad lista med insättningssortering

Följande Java-program visar sorteringen av en enstaka länkad lista med insättningssorteringen.

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:

Originallänkad lista:
1 8 32 2 10
Sorterad länkad lista:
1 2 8 10 32

output - Länkad lista

I ovanstående program har vi definierat en klass som skapar en länkad lista och lägger till noder till den samt sorterar den. Eftersom den enskilt länkade listan har nästa pekare är det lättare att hålla reda på noder när du sorterar listan.

Sortera en dubbelt länkad lista med insättningssortering

Följande program sorterar en dubbelt länkad lista med hjälp av Insertion sort. Observera att eftersom den dubbelt länkade listan har både föregående och nästa pekare är det enkelt att uppdatera och länka pekarna medan data sorteras.

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:

Original dubbelt länkad lista:
1 11 2 7 3 5
Sorterad dubbelt länkad lista:
1 2 3 5 7 11

Output - dubbelt länkad lista

Vanliga frågor

F # 1) Vad är insättningssortering i Java?

Svar: Insättningssortering är en enkel sorteringsteknik i Java som är effektiv för en mindre datamängd och på plats. Det antas att det första elementet alltid sorteras och sedan jämförs varje efterföljande element med alla dess tidigare element och placeras i rätt läge.

F # 2) Varför är Insertion Sort bättre?

Svar: Insättningssortering är snabbare för mindre datamängder när andra tekniker som snabb sortering lägger till omkostnader genom rekursiva samtal. Insättningssortering är jämförelsevis mer stabil än de andra sorteringsalgoritmerna och kräver mindre minne. Insättningssortering fungerar också mer effektivt när arrayen nästan är sorterad.

F # 3) Vad används Insertion Sort för?

Svar: Insättningssortering används mest i datorprogram som bygger komplexa program som filsökning, sökning och datakomprimering.

F # 4)Vad är effektiviteten med insättningssortering?

hur man öppnar en bittorrent-fil

Svar: Insättningssortering har en genomsnittlig fallprestanda på O (n ^ 2). Det bästa fallet för insättningssortering är när matrisen redan är sorterad och den är O (n). Värsta fallet för insättningssortering är igen O (n ^ 2).

Slutsats

Insättningssortering är en enkel sorteringsteknik som fungerar på Arrays eller länkade listor. Det är användbart när datamängden är mindre. När datamängden blir större blir denna teknik långsammare och ineffektiv.

Insättningssorten är också mer stabil och på plats än de andra sorteringsteknikerna. Det finns inget minne över huvudet eftersom ingen separat struktur används för att lagra sorterade element.

Insättningssortering fungerar bra på att sortera länkade listor som är både enstaka och dubbelt länkade listor. Detta beror på att den länkade listan består av noder som är anslutna via pekare. Därför blir sortering av noder enklare.

I vår kommande handledning kommer vi att diskutera ännu en sorteringsteknik i Java.

=> Läs igenom Easy Java Training Series.

Rekommenderad läsning

^