Eine Einführung in den Insertionssortalgorithmus
Insertion Sort ist eine Technik, die funktioniert, indem sie eine sortierte Unterliste verwendet und ihr kontinuierlich einen Wert aus der unsortierten Liste hinzufügt, bis die gesamte Liste sortiert ist.
Der Algorithmus beginnt mit dem ersten Listenelement als sortierte Unterliste. Es vergleicht dann die nächste Zahl mit der ersten. Wenn es größer ist, wird es in den ersten Index eingefügt. Andernfalls wird es in seinem Index belassen.
Der dritte Wert wird dann mit den anderen beiden verglichen und dann in den richtigen Index eingefügt. Dieser Vorgang wird fortgesetzt, bis die gesamte Liste sortiert ist.
Ein genauerer Blick auf die Einfügungssortierung
Die obige Beschreibung hat für Sie möglicherweise keinen Sinn gemacht. Ein Beispiel sollte Ihnen helfen, viel besser zu verstehen.
Angenommen, Sie haben eine Liste: [39, 6, 2, 51, 30, 42, 7].
Der Algorithmus identifiziert 39 als ersten Wert der sortierten Unterliste. Die Auswertung geht dann auf die zweite Position über.
6 wird dann mit 39 verglichen. Da 6 kleiner als 39 ist, wird 6 an erster Stelle und 39 an zweiter Stelle eingefügt. Die neue Listenreihenfolge ist nach dem ersten Durchlauf jetzt:
[6, 39, 2, 51, 30, 42, 7]
Die Auswertung verschiebt sich nun auf die dritte Position. 2 wird mit den letzten beiden Zahlen verglichen und dann an der richtigen Stelle eingefügt. Die neue Listenreihenfolge ist nach dem zweiten Durchgang jetzt:
[2, 6, 39, 51, 30, 42, 7]
Für den dritten Durchgang ist die Listenreihenfolge:
[2, 6, 39, 51, 30, 42, 7]
Der Vorgang wiederholt sich, bis die gesamte Liste sortiert ist.
Siehe das Diagramm unten, das diese Operationen zusammenfasst:
Algorithmusanalyse
Die Zeitkomplexität von Insertion Sort ist O(n 2 ), genau wie Bubblesort . Die Anzahl der Vergleiche im Worst-Case-Szenario ist die Summe aller ganzen Zahlen von 1 bis (n-1), was eine quadratische Summe ergibt.
Codeimplementierung
Der folgende Python- und Java-Code zeigt, wie Sie die Insertion Sort-Methode implementieren können.
Python:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x < n; x++) {
int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}Bessere Codierung mit Pseudocode
Die obigen Codebeispiele wurden ohne Pseudocode angegeben, auf den Sie verweisen können, um diesen Algorithmus in anderen Sprachen zu schreiben. Die meisten Programmierer (einschließlich des Autors) laufen gerne zu ihren Tastaturen, nachdem ihnen "geflüstert" wurde, wie ein Programm funktioniert.
Dieser Ansatz ist leider fehleranfällig, da die Programmlogik komplizierter wird. Wie möchten Sie Ihr Programmierspiel verbessern, indem Sie lernen, wie man Pseudocode verwendet?