Einführung in Insertion Sort in Java
Wenn Sie ein Programmierer sind, müssen Sie schon viel über das Sortieren gehört haben. Beim Sortieren werden die Elemente in aufsteigender oder absteigender Reihenfolge angeordnet. Es gibt so viele Sortieralgorithmen, die zum Sortieren der Elemente zur Verfügung stehen, und jeder Algorithmus verfügt über unterschiedliche Sortiermethoden und eine unterschiedliche Komplexität. Es hängt also vom konkreten Szenario und der Anzahl der Elemente ab, welcher Algorithmus verwendet werden soll. Das Einfügen ist auch einer der allgemein verwendeten Sortieralgorithmen mit der Komplexität von O (n 2) und wird so ausgeführt, als würden wir die Spielkarten in unseren Händen sortieren. In diesem Thema lernen wir Insertion Sort in Java kennen.
Wie funktioniert die Einfügesortierung in Java?
Lassen Sie uns die Funktionsweise von Insertion sort anhand eines Beispiels verstehen. Angenommen, es gibt ein Array mit dem Namen arr, das die folgenden Elemente enthält:
10 5 8 20 30 2 9 7
Schritt # 1 - Einfügesortierung beginnt mit dem 2. Element des Arrays, dh 5, wobei das 1. Element des Arrays in sich selbst sortiert wird. Jetzt wird das Element 5 mit 10 verglichen, da 5 kleiner als 10 ist. 10 wird also um eine Position nach vorne verschoben und 5 wird davor eingefügt.
Das resultierende Array lautet nun:
5 10 8 20 30 2 9 7
Schritt # 2 - Nun wird das Element arr (2), dh 8, mit dem Element arr (1), dh 10, verglichen. Da 8 kleiner als sein vorhergehendes Element 10 ist, wird es von seiner Position einen Schritt voraus verschoben und dann ist es verglichen mit 5. Da 8 größer als 5 ist, wird es danach eingefügt.
Dann ist das resultierende Array:
5 8 10 20 30 2 9 7
Schritt # 3 - Jetzt wird das Element 20 mit 10 verglichen, da es größer als 10 ist und in seiner Position bleibt.
5 8 10 20 30 2 9 7
Schritt Nr. 4 - Element 30 wird mit 20 verglichen, und da es größer als 20 ist, würden keine Änderungen vorgenommen, und das Array bleibt unverändert. Jetzt wäre das Array
5 8 10 20 30 2 9 7
Schritt # 5 - Element 2 wird mit 30 verglichen, da es kleiner als 30 ist, es wird eine Position vorwärts verschoben, dann wird es mit 20, 10, 8, 5 nacheinander verglichen und alle Elemente werden um eine Position vorwärts verschoben und 2 wird vor 5 eingefügt.
Das resultierende Array ist:
2 5 8 10 20 30 9 7
Schritt 6 - Element 9 wird mit 30 verglichen, da es kleiner als 30 ist, es wird mit 20, 10 nacheinander verglichen und das Element wird um eine Position vor und 9 vor 10 und nach 8 eingefügt. Das resultierende Array ist:
2 5 8 9 10 20 30 7
Schritt Nr. 7 - Element 7 wird mit 30 verglichen und da es kleiner als 30 ist, wird es mit 30, 20, 10, 9, 8 verglichen und alle Elemente werden um eine Position nach der anderen verschoben und 7 wird vor 8 eingefügt Das resultierende Array würde:
2 5 7 8 9 10 20 30
Auf diese Weise werden alle Elemente des Arrays mithilfe der Einfügesortierung sortiert, wobei der Vergleich mit dem vorherigen Element beginnt.
Beispiele zur Implementierung von Insertion Sort in Java
Insertion Sort in Java ist ein einfacher Sortieralgorithmus, der für alle kleinen Datenmengen geeignet ist.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Ausgabe:
12 15 18 21 23 52 61
Erläuterung:
In dem obigen Programm von Insertion Sort wird die InsertionSort () - Funktion verwendet, um die Elemente des ursprünglichen Arrays zu sortieren. Die Sortierung beginnt ab dem zweiten Element, da das erste Element als in sich selbst sortiert betrachtet wird. Die Schleife von 'j' beginnt also mit dem Index 1 des Arrays. 'i' ist die Variable, die den Index unmittelbar vor dem 'j' verfolgt, um den Wert zu vergleichen. ' key 'ist die Variable, die den Wert des aktuellen Elements enthält, das sortiert angeordnet werden soll. Die Schleife while () wird ausgeführt, wenn der aktuelle Wert kleiner als der ganz linke Wert ist, damit die Verschiebung von Elementen verarbeitet und am Ende die Einfügung des aktuellen Elements an der rechten Position ausgeführt werden kann. Die Funktion printArray () dient zum endgültigen Drucken des sortierten Arrays.
1. Bester Fall
Bei der Einfügesortierung ist es am besten, wenn alle Elemente des Arrays bereits sortiert sind. Wenn also ein Element mit seinem am weitesten links stehenden Element verglichen wird, ist es immer größer und daher wird keine Verschiebung und Einfügung von Elementen verarbeitet. In diesem Fall wäre die Komplexität des besten Falls linear, dh O (n).
2. Der schlimmste Fall
Im obigen Code der Einfügesortierung wäre der schlimmste Fall, wenn sich das Array in umgekehrter Reihenfolge befindet, sodass es jedes Mal, wenn das Element mit seinem am weitesten links liegenden Element verglichen wird, kleiner ist und dann mit allen ablaufenden Elementen verglichen wird, die stattfinden und sich verschieben und das Einfügen ist fertig. In diesem Fall ist die Komplexität der Einfügesorte O (n 2).
3. Durchschnittlicher Fall
Selbst in einem durchschnittlichen Fall hat die Einfügungssortierung eine Komplexität von 0 (n 2), in der einige Elemente nicht verschoben werden müssen, während einige Elemente von ihren Positionen verschoben werden und die Einfügung an der richtigen Position ausgeführt wird.
4. Beste Verwendung
Einfügesortierung ist am besten zu verwenden, wenn die Größe eines Arrays nicht sehr groß ist oder nur eine kleine Anzahl von Elementen sortiert werden muss, in denen fast alle Elemente sortiert sind und nur einige Änderungen vorgenommen werden müssen. Die Einfügesortierung ist einer der schnellsten Algorithmen für kleine Arrays, sogar schneller als die Schnellsortierung. Tatsächlich verwendet quicksort Insertion sort, um die kleinen Teile des Arrays zu sortieren.
Fazit
Die obige Erklärung zeigt deutlich die Arbeitsweise und die Implementierung von Insertion Sort in Java. Auch in anderen Programmiersprachen bleibt die Logik zur Durchführung der Einfügesortierung dieselbe, nur die Syntax ändert sich. Vor der Implementierung eines Sortieralgorithmus ist es sehr wichtig, eine Analyse des Szenarios durchzuführen, in dem die Sortierung durchgeführt werden muss, da nicht jeder Sortieralgorithmus in alle Szenarios passt.
Empfohlene Artikel
Dies ist eine Anleitung zum Sortieren von Einfügungen in Java. Hier wird erläutert, wie das Sortieren von Einfügungen in Java mit Beispielen zum Implementieren von Sortieren von Einfügungen in Java funktioniert. Sie können sich auch die folgenden Artikel ansehen, um mehr zu erfahren -
- Quadratwurzel in Java
- BorderLayout in Java
- Reverse Number in Java
- StringBuffer in Java
- Quadratwurzel in PHP
- Quadratwurzel in JavaScript
- Leitfaden zu den wichtigsten 6 Sortieralgorithmen in Python