Insertionssortierung
Insertionssortierung, auch allgemein als direkte Einfügesortierung bekannt, ist ein effizienter Algorithmus zum Sortieren einer kleinen Anzahl von Elementen.
Die Insertionssortierung ist eine der einfachsten Sortiermethoden. Ihre Grundidee besteht darin, einen Datensatz in eine bereits sortierte geordnete Tabelle einzufügen und dadurch eine neue geordnete Tabelle zu bilden, bei der die Anzahl der Datensätze um 1 erhöht wird.
In ihrer Implementierung wird eine doppelte Schleife verwendet. Die äußere Schleife iteriert über alle Elemente außer dem ersten, und die innere Schleife sucht die Einfügeposition in der geordneten Tabelle vor dem aktuellen Element und führt Verschiebungen durch.
Funktionsweise
Die Kernidee der Insertionssortierung ist„Aufbau einer geordneten Sequenz“Sie teilt das zu sortierende Array (oder die Liste) logisch in zwei Teile auf:
- Sortierter TeilAnfangs wird das erste Element des Arrays üblicherweise als eigenständige geordnete Sequenz betrachtet.
- Unsortierter TeilVom zweiten Element bis zum letzten Element.
Der Algorithmus wirdwiederholt das erste Element des unsortierten Teils an der richtigen Position des sortierten Teils einfügen.Bis der unsortierte Teil leer wird, ist das gesamte Array sortiert.
Anwendbarkeit
Die durchschnittliche Zeitkomplexität der Insertionssortierung ist ebenfallsO(n^2), und die Raumkomplexität ist von konstanter OrdnungO(1)Die konkrete Zeitkomplexität hängt auch von der Vorsortierung des Arrays ab.
Bei der Insertionssortierung ist der optimale Fall gegeben, wenn das zu sortierende Array bereits geordnet ist. Man muss nur die aktuelle Zahl mit der vorherigen Zahl vergleichen, und die Gesamtzahl der zu diesem Zeitpunkt benötigten Vergleiche beträgtN-1Mal, und die Zeitkomplexität istO(N)Der schlechteste Fall ist, wenn das zu sortierende Array in umgekehrter Reihenfolge vorliegt. Zu diesem Zeitpunkt ist die Anzahl der Vergleiche am größten. Der schlechteste Fall istO(n^2)。
Prozessdiagramm
Angenommen, die vorherigenn-1(wobein>=2) Zahlen sind bereits sortiert. Nun füge dienZahl in die zuvor sortierte Sequenz ein, finde dann ihre passende Position, sodass die Sequenz nach dem Einfügen der n-ten Zahl ebenfalls sortiert ist.
Der Prozess, alle Elemente auf diese Weise einzufügen, bis die gesamte Sequenz sortiert ist, wird Insertionssortierung genannt.
Der gesamte Prozess der Insertionssortierung von klein nach groß ist in der Abbildung dargestellt:
Erster Durchlauf:Ausgehend von der 6 an der zweiten Position ist sie kleiner als die 7 davor, also werden die Positionen getauscht.
Zweiter Durchlauf:Die 9 an der dritten Position ist größer als die 7 an der vorherigen Position, also ist kein Tausch erforderlich.
Dritter Durchgang:Die 3 an der vierten Position ist kleiner als die 9 an der vorherigen Position, also die Positionen tauschen und eins nach dem anderen nach vorne vergleichen.
Vierter Durchgang:Die 1 an der fünften Position ist kleiner als die 9 an der vorherigen Position, die Positionen tauschen, dann eins nach dem anderen nach vorne vergleichen.
......
Auf diese Weise vergleicht man eins nach dem anderen bis zum letzten Element.
Java-Beispielcode
Quellcode-Paket-Download:Herunterladen
Teilcode:
Code der Datei InsertionSort.java:
/**
* Insertionsort
*/
public class InsertionSort {
// Kerncode --- Start
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// Finde die geeignete Einfügeposition für Element arr[i]
for( int j = i ; j > 0 ; j -- )
if( arr[j].compareTo( arr[j-1] ) < 0 )
swap( arr, j , j-1 );
else
break;
}
}
// Kerncode --- Ende
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
InsertionSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}
Algorithmusimplementierung und Codeanalyse
Nachdem wir das Prinzip verstanden haben, schauen wir uns die konkrete Codeimplementierung an. Hier bieten wir Versionen in zwei gängigen Sprachen an: Python und Java.
Python-Implementierung
Beispiel
"""
Implementierung des Insertion-Sort-Algorithmus (aufsteigende Reihenfolge)
:param arr: Die zu sortierende Liste
:return: Die sortierte Liste (an Ort und Stelle geändert, ebenfalls zurückgegeben)
"""
# Vom zweiten Element bis zum letzten Element durchlaufen (Index 1 bis n-1)
for i in range(1, len(arr)):
current_value = arr[i] # Das aktuelle einzufügende Element, zunächst "in der Hand gehalten"
j = i - 1 # j zeigt auf das letzte Element der sortierten Sequenz
# Innere Schleife: Finde die Einfügeposition für current_value im sortierten Teil arr[0..i-1]
# Bedingung 1: j >= 0 stellt sicher, dass der Index nicht vor den Listenanfang gerät (kein Out-of-Bounds)
# Bedingung 2: arr[j] > current_value bedeutet, dass das aktuell verglichene Element größer als das "gehaltene" ist und nach hinten verschoben werden muss
while j >= 0 and arr[j] > current_value:
arr[j + 1] = arr[j] # Das größere Element um eine Position nach hinten verschieben, um Platz zu schaffen
j -= 1 # Vergleiche weiter mit dem nächsten Element nach links
# Schleife endet, d. h. die Einfügeposition (j+1) ist gefunden
# An diesem Punkt gilt arr[j] <= current_value oder j == -1
arr[j + 1] = current_value # Das "gehaltene" Element an die richtige Position einfügen
return arr
# Testcode
if __name__ == "__main__":
# Testdaten
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Vor dem Sortieren:", test_data)
sorted_data = insertion_sort(test_data.copy()) # Mit einer Kopie sortieren, damit die Originaldaten unverändert bleiben
print("Nach dem Sortieren:", sorted_data)
# Ein weiterer Test: nahezu sortierte Daten
nearly_sorted_data = [1, 3, 2, 4, 6, 5, 8, 7]
print("\n"Nahezu sortierte Daten vor dem Sortieren:", nearly_sorted_data)
print("Nahezu sortierte Daten nach dem Sortieren:", insertion_sort(nearly_sorted_data.copy()))
Java-Implementierung
Beispiel
public static void insertionSort(int[] arr) {
# Vom zweiten Element bis zum letzten Element durchlaufen (Index 1 bis n-1)
for (int i = 1; i < arr.length; i++) {
int currentValue = arr[i]; # Aktuelles Element zum Einfügen
int j = i - 1; # j zeigt auf das letzte Element der sortierten Sequenz
# Innere Schleife: Einfügeposition finden und Elemente verschieben
while (j >= 0 && arr[j] > currentValue) {
arr[j + 1] = arr[j]; # Element nach rechts verschieben
j--;
}
# Aktuelles Element an der richtigen Position einfügen
arr[j + 1] = currentValue;
}
}
# Überladene Methode, unterstützt das Sortieren eines Teilbereichs eines Integer-Arrays
public static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int currentValue = arr[i];
int j = i - 1;
while (j >= left && arr[j] > currentValue) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = currentValue;
}
}
public static void main(String[] args) {
# Testdaten
int[] testData = {64, 34, 25, 12, 22, 11, 90};
System.out.print("Vor dem Sortieren: ");
printArray(testData);
int[] dataToSort = testData.clone(); # Eine Kopie verwenden
insertionSort(dataToSort);
System.out.print("Nach dem Sortieren: ");
printArray(dataToSort);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
Analyse der Algorithmusmerkmale
Das Verständnis der Leistung und der Anwendungsszenarien eines Algorithmus ist entscheidend. Die Eigenschaften von Insertionsort lassen sich wie folgt zusammenfassen:
| Funktionen | Beschreibung | Erklärung |
|---|---|---|
| Zeitkomplexität | Durchschnitts- und Worst-Case-Fall: $O(n^2)$ | Verschachtelte Schleifen sind erforderlich, um Elemente zu vergleichen und zu verschieben. Für n Elemente erfordert der Worst Case (vollständig umgekehrte Reihenfolge) etwa $\frac{n(n-1)}{2}$ Vergleiche und Verschiebungen. |
| Bester Fall：$O(n)$ | Wenn das Eingabe-Array bereits im Wesentlichen sortiert ist, wird die innere Schleife selten ausgeführt oder bricht sofort ab, und es sind nur n-1 Vergleiche erforderlich. | |
| Speicherkomplexität | $O(1)$ | JaIn-Place-Sortieralgorithmus, der nur zusätzlichen Speicherplatz in konstanter Größenordnung benötigt (wiecurrent_value, jund andere Variablen). |
| Stabilität | Stabil | Wenn zwei Elemente gleich sind, bleibt ihre relative Reihenfolge nach dem Sortieren unverändert. Denn der Algorithmus verschiebt Elemente nur dann, wenn er auf einen Wert stößt, dergrößer alsder aktuelle Wert ist. |
| Anwendbare Szenarien | 1. Kleine Datenmengen 2. Die Daten sind im Wesentlichen sortiert 3. Als Unterroutine für fortgeschrittene Sortieralgorithmen (wie Quicksort, Mergesort) |
In diesen Fällen können seine einfache Logik und sein geringer konstanter Overhead dazu führen, dass es besser abschneidet als komplexere $O(n \log n)$-Algorithmen. |
Herleitung der Formel für die Zeitkomplexität (Worst Case)
Im Worst Case (Array in vollständig umgekehrter Reihenfolge):
- Das 1. Element (Index 0) wird eingefügt, 0-mal verglichen.
- Das 2. Element (Index 1) wird eingefügt, 1-mal verglichen, 1-mal verschoben.
- Das 3. Element (Index 2) wird eingefügt, 2-mal verglichen, 2-mal verschoben.
- ...
- Das n-te Element (Index n-1) wird eingefügt, n-1-mal verglichen, n-1-mal verschoben.
Die Gesamtzahl der Vergleiche und Verschiebungen beträgt: $0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2}$
Daher beträgt die Zeitkomplexität $O(n^2)$.