Insertion Sort Algorithmus in Java mit Programmbeispiel

Was ist ein Einfügungssortierungsalgorithmus?

Einfügungssortierung ist ein einfacher Sortieralgorithmus, der für kleine Datensätze geeignet ist. Während jeder Iteration führt der Algorithmus Folgendes aus:

• Entfernt ein Element aus einem Array.
• Vergleicht es mit dem größten Wert im Array.
• Verschiebt das Element an die richtige Position.

Das Verhalten ähnelt der Art und Weise, wie ein Kartenspieler seine Karten anordnet: Jede neue Karte wird aufgenommen und nach links an allen größeren Karten vorbeigeschoben, bis sie an der richtigen Stelle liegt. Da alle Verschiebungen innerhalb des ursprünglichen Arrays stattfinden, ist der Einfügesortieralgorithmus sowohl in-place als auch stabil.

Es gehört zur selben Familie von Anfängerfreundlichen Java Sortierroutinen als Blase sortierenAllerdings führt es normalerweise weitaus weniger Schreibvorgänge auf Daten durch, die bereits teilweise geordnet sind.

Prozess des Einfügungssortieralgorithmus

So funktioniert der Einfügesortieralgorithmus grafisch:

Die Animation wiederholt dieselben drei Schritte. Java Das unten stehende Programm wird ausgeführt. Die Trockenlauftabelle tracFühre diese Schritte am Beispielarray {860, 8, 200, 9} genau so aus, wie das Programm sie zur Laufzeit ausgibt.

Beachten Sie, dass im dritten Durchlauf zwei Vergleiche erforderlich sind, da der Schlüssel 9 zwei größere Werte passieren muss. Die Anzahl der Vergleiche steigt daher mit der Abweichung der Elemente von der ursprünglichen Reihenfolge.

Java Programmbeispiel zum Sortieren eines Arrays mithilfe des Insertionsort-Algorithmus:

Das folgende Programm sortiert das Array {860, 8, 200, 9} und gibt einen fortlaufenden Kommentar aus, sodass jeder Vergleich und jede Verschiebung sichtbar ist. Speichern Sie es unter dem Namen InsertionSortExample.java und kompilieren Sie es mit einer beliebigen JDK 8- oder späteren Version.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Die Ausführung der Klasse erzeugt Folgendes: trace ist hier abgebildet. Jedes Sortierpassnummer Die erste Zeile markiert eine Iteration der äußeren Schleife, und die nach jedem Tausch ausgegebene Zeile zeigt das Array in seinem aktuellen Zustand.

Code Ausgang:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

Zeit- und Speicherkomplexität des Einfügesortierverfahrens

Die Leistung des Insertionsort-Algorithmus hängt stark davon ab, wie geordnet die Eingabe bereits ist. Deshalb unterscheiden sich der beste und der schlechteste Fall um eine ganze Größenordnung.

Die Raumnutzung ist wesentlich einfacher. Nur die Zähler i, j, n und key werden erstellt und das Array wird an Ort und Stelle neu angeordnet, sodass der zusätzliche Speicherplatz unabhängig von der Größe der Eingabe O(1) beträgt.

Da die innere Schleife stoppt, sobald sie auf einen kleineren Wert trifft, wird Insertion Sort als adaptiv bezeichnet: Je näher die Eingabe an der sortierten Reihenfolge liegt, desto mehr nähert sich die Laufzeit einem linearen Wert an.

Vor- und Nachteile des Einfügesortierverfahrens

Insertionsort hat sich trotz seines quadratischen Mittelwerts in Produktionsbibliotheken behauptet, weil seine konstanten Faktoren winzig sind und sein Verhalten vorhersehbar ist.

Vorteile

• Einfach zu schreiben und leicht zu trace von Hand, was es sowohl für den Unterricht als auch für Vorstellungsgespräche geeignet macht.
• Stabil, sodass Datensätze, die denselben Schlüssel verwenden, ihre ursprüngliche relative Reihenfolge beibehalten.
• In-Place, benötigt nur O(1) zusätzlichen Speicher über das Eingabe-Array hinaus.
• Adaptiv, erreicht O(n) bei Daten, die bereits nahezu sortiert sind.
• Online, was bedeutet, dass es eine Liste sortieren kann, während noch neue Elemente eintreffen.

Nachteile

• Die quadratische Laufzeit bei zufälligen oder umgekehrt geordneten Eingaben macht es für große Arrays ungeeignet.
• Bei jedem Shift-Vorgang werden Daten in das Array geschrieben, sodass mehr Daten verschoben werden als beim Selection Sort.
• Mergesort und Quicksort sind deutlich schneller, sobald die Eingabe einige Dutzend Elemente überschreitet.

Eine praktische Regel ist, den Insertion Sort zu verwenden, wenn das Array klein ist, wenn die Daten fast geordnet sind oder wenn ein Divide-and-Conquer-Sort eine Partition auf eine Handvoll Elemente reduziert hat.

Einfügesortierung vs. Bubble Sort vs Selection Sort

Alle drei Algorithmen sind quadratische Vergleichssortierverfahren, unterscheiden sich jedoch in ihrer Stabilität, in ihrer Reaktion auf geordnete Eingaben und in der Anzahl der Schreibvorgänge.

Selection Sort ist im Vorteil, wenn Schreibvorgänge aufwändig sind, da es die wenigsten Vertauschungen durchführt. Insertion Sort ist in diesem Umfang fast überall überlegen, insbesondere bei teilweise sortierten Daten. Aus diesem Grund werden Bibliotheksortieralgorithmen wie der hinter [Name des Algorithmus] häufig verwendet. verbreitet Java Übungen und die internen JDK-Funktionen greifen bei sehr kleinen Partitionen darauf zurück.

Häufig gestellte Fragen