Menü

Einfügungssortierung in Java - Einfügungssortierungsalgorithmus und Beispiele

  • Haupt
  • Andere
  • Einfügungssortierung in Java - Einfügungssortierungsalgorithmus und Beispiele

insertion sort java insertion sort algorithm examples

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

In diesem Lernprogramm wird die Einfügungssortierung in Java erläutert, einschließlich des Algorithmus, des Pseudocodes und der Beispiele für Sortierarrays sowie der einfach verknüpften und doppelt verknüpften Liste:

Die Technik des Einfügungssortierungsalgorithmus ähnelt der Blasensortierung, ist jedoch etwas effizienter. Die Einfügungssortierung ist praktikabler und effektiver, wenn eine kleine Anzahl von Elementen beteiligt ist. Wenn der Datensatz größer ist, dauert das Sortieren der Daten länger.

=> Schauen Sie sich hier den Java Beginners Guide an.

wie man sort in java benutzt

Einfügungssortierung in Java

Was du lernen wirst:

Einführung in das Einfügen Sortieren in Java

Bei der Einfügesortiertechnik nehmen wir an, dass das erste Element in der Liste bereits sortiert ist, und beginnen mit dem zweiten Element. Das zweite Element wird mit dem ersten verglichen und ausgetauscht, wenn dies nicht der Fall ist. Dieser Vorgang wird für alle nachfolgenden Elemente wiederholt.

Im Allgemeinen vergleicht die Einfügesortiertechnik jedes Element mit allen vorherigen Elementen und sortiert das Element, um es an der richtigen Position zu platzieren.

Wie bereits erwähnt, ist die Insertion-Sortiertechnik für einen kleineren Datensatz praktikabler, und daher können Arrays mit einer kleinen Anzahl von Elementen unter Verwendung einer effizienten Insertion-Sortierung sortiert werden.

Die Einfügesortierung ist besonders nützlich beim Sortieren von Datenstrukturen verknüpfter Listen. Wie Sie wissen, haben verknüpfte Listen Zeiger, die auf das nächste Element (einfach verknüpfte Liste) und das vorherige Element (doppelt verknüpfte Liste) verweisen. Dies erleichtert das Verfolgen der vorherigen und nächsten Elemente.

Daher ist es einfacher, die Einfügesortierung zum Sortieren verknüpfter Listen zu verwenden. Das Sortieren nimmt jedoch viel Zeit in Anspruch, wenn die Datenelemente mehr sind.

In diesem Tutorial werden wir die Insertion-Sortiertechnik einschließlich ihres Algorithmus, Pseudocodes und Beispielen diskutieren. Wir werden auch Java-Programme implementieren, um ein Array, eine einfach verknüpfte Liste und eine doppelt verknüpfte Liste mithilfe der Einfügesortierung zu sortieren.

Einfügungssortierungsalgorithmus

Der Einfügungssortieralgorithmus ist wie folgt.

Schritt 1 : Wiederholen Sie die Schritte 2 bis 5 für K = 1 bis N-1

Schritt 2 : setze temp = A (K)

Schritt 3 : setze J = K - 1

Schritt 4 ::

Wiederholen, während temp<=A(J)
setze A (J + 1) = A (J)
setze J = J - 1
(Ende der inneren Schleife)

Schritt 5 ::

setze A (J + 1) = temp
(Ende der Schleife)

Schritt 6 : Ausfahrt

Wie Sie wissen, beginnt die Einfügesortierung mit dem zweiten Element, vorausgesetzt, das erste Element ist bereits sortiert. Die obigen Schritte werden ab dem zweiten Element für alle Elemente in der Liste wiederholt und an die gewünschten Positionen gebracht.

Pseudocode für Einfügesortierung

Der Pseudocode für die Einfügesortiertechnik ist unten angegeben.

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

Als nächstes sehen wir uns eine Abbildung an, die das Sortieren eines Arrays mithilfe der Einfügesortierung veranschaulicht.

Sortieren eines Arrays mithilfe der Einfügesortierung

Nehmen wir ein Beispiel für die Einfügungssortierung mithilfe eines Arrays.

Das zu sortierende Array lautet wie folgt:

zu sortierendes Array

Jetzt vergleichen wir für jeden Durchgang das aktuelle Element mit allen vorherigen Elementen. Im ersten Durchgang beginnen wir also mit dem zweiten Element.

Vergleichen Sie das 2. Element mit dem 1. Element

Pass 2

Pass 3

Pass 4

Pass 5

Pass 6

Daher benötigen wir N Durchgänge, um ein Array mit N Elementen vollständig zu sortieren.

So öffnen Sie eine Java-Datei

Die obige Abbildung kann in tabellarischer Form wie folgt zusammengefasst werden:

BestehenUnsortierte ListeVergleichSortierte Liste
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
zwei{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}

Wie in der obigen Abbildung gezeigt, befindet sich am Ende jedes Durchgangs ein Element an der richtigen Stelle. Um N Elemente an ihrer richtigen Stelle zu platzieren, benötigen wir im Allgemeinen N-1-Durchgänge.

Implementierung der Einfügesortierung in Java

Das folgende Programm zeigt die Implementierung der Einfügesortierung in Java. Hier haben wir ein Array, das mit der Einfügesortierung sortiert werden soll.

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

Ausgabe:

Ursprüngliches Array: (10, 6, 15, 4, 1, 45)
Sortiertes Array: (1, 4, 6, 10, 15, 45)

Implementierung von Insertion Sort - Output

In der obigen Implementierung ist zu sehen, dass die Sortierung von 2 beginntndElement des Arrays (Schleifenvariable j = 1) und dann wird das aktuelle Element mit allen vorherigen Elementen verglichen. Das Element wird dann an der richtigen Position platziert.

Die Einfügesortierung funktioniert effektiv für kleinere Arrays und für Arrays, die teilweise sortiert sind und bei denen die Sortierung in weniger Durchgängen abgeschlossen ist.

Die Einfügesortierung ist eine stabile Sortierung, d. H. Sie behält die Reihenfolge gleicher Elemente in der Liste bei.

Was ist der Unterschied zwischen Java und C ++

Sortieren einer verknüpften Liste mithilfe der Einfügesortierung

Das folgende Java-Programm zeigt das Sortieren einer einfach verknüpften Liste mithilfe der Einfügesortierung.

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

Ausgabe:

Ursprüngliche verknüpfte Liste:
1 8 32 2 10
Sortierte verknüpfte Liste:
1 2 8 10 32

Ausgabe - Verknüpfte Liste

Im obigen Programm haben wir eine Klasse definiert, die eine verknüpfte Liste erstellt, Knoten hinzufügt und diese sortiert. Da die einfach verknüpfte Liste einen nächsten Zeiger hat, ist es einfacher, beim Sortieren der Liste die Knoten zu verfolgen.

Sortieren einer doppelt verknüpften Liste mithilfe der Einfügesortierung

Das folgende Programm sortiert eine doppelt verknüpfte Liste mithilfe der Einfügesortierung. Da die doppelt verknüpfte Liste sowohl vorherige als auch nächste Zeiger enthält, ist es einfach, die Zeiger beim Sortieren der Daten zu aktualisieren und erneut zu verknüpfen.

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

Ausgabe:

Ursprüngliche doppelt verknüpfte Liste:
1 11 2 7 3 5
Sortierte doppelt verknüpfte Liste:
1 2 3 5 7 11

Ausgabe - Doppelt verknüpfte Liste

Häufig gestellte Fragen

F # 1) Was ist Insertion Sort in Java?

Antworten: Die Einfügesortierung ist eine einfache Sortiertechnik in Java, die für einen kleineren Datensatz effizient und vorhanden ist. Es wird angenommen, dass das erste Element immer sortiert ist und dann jedes nachfolgende Element mit allen vorherigen Elementen verglichen und an der richtigen Position platziert wird.

Q # 2) Warum ist Insertion Sort besser?

Antworten: Die Einfügesortierung ist für kleinere Datensätze schneller, wenn andere Techniken wie die schnelle Sortierung durch rekursive Aufrufe zusätzlichen Aufwand verursachen. Die Einfügesortierung ist vergleichsweise stabiler als die anderen Sortieralgorithmen und benötigt weniger Speicher. Die Einfügesortierung funktioniert auch effizienter, wenn das Array fast sortiert ist.

Q # 3) Wofür wird die Einfügesortierung verwendet?

Antworten: Die Einfügesortierung wird hauptsächlich in Computeranwendungen verwendet, die komplexe Programme wie Dateisuche, Pfadfindung und Datenkomprimierung erstellen.

Q # 4)Was ist die Effizienz von Insertion Sort?

Antworten: Die Einfügesortierung hat eine durchschnittliche Fallleistung von O (n ^ 2). Der beste Fall für die Einfügesortierung ist, wenn das Array bereits sortiert ist und O (n) ist. Die schlechteste Leistung für die Einfügesortierung ist wieder O (n ^ 2).

Fazit

Die Einfügesortierung ist eine einfache Sortiertechnik, die für Arrays oder verknüpfte Listen funktioniert. Dies ist nützlich, wenn der Datensatz kleiner ist. Wenn der Datensatz größer wird, wird diese Technik langsamer und ineffizienter.

Die Einfügesortierung ist außerdem stabiler und vorhandener als die anderen Sortiertechniken. Es gibt keinen Speicheraufwand, da keine separate Struktur zum Speichern sortierter Elemente verwendet wird.

Die Einfügesortierung eignet sich gut zum Sortieren verknüpfter Listen, die sowohl einfach als auch doppelt verknüpfte Listen sind. Dies liegt daran, dass die verknüpfte Liste aus Knoten besteht, die über Zeiger verbunden sind. Dadurch wird das Sortieren von Knoten einfacher.

In unserem nächsten Tutorial werden wir eine weitere Sortiertechnik in Java diskutieren.

=> Lesen Sie die Easy Java Training Series durch.

Literatur-Empfehlungen

^