Es gibt mehrere grundlegende Algorithmen, um das Problem des Sortierens eines Arrays zu lösen. Eine der bekanntesten unter ihnen ist Insertion Sort. Aufgrund ihrer Übersichtlichkeit und Einfachheit, aber geringen Effizienz, wird diese Methode hauptsächlich im Programmierunterricht eingesetzt. Es ermöglicht Ihnen, die grundlegenden Sortiermechanismen zu verstehen.
Beschreibung des Algorithmus
Die Essenz des Insertion-Sort-Algorithmus besteht darin, dass ein richtig geordnetes Segment innerhalb des anfänglichen Arrays gebildet wird. Jedes Element wird einzeln mit dem überprüften Teil verglichen und an der richtigen Stelle eingefügt. Nachdem alle Elemente durchlaufen wurden, reihen sie sich also in der richtigen Reihenfolge auf.
Die Reihenfolge der Auswahl der Elemente kann beliebig sein, sie können willkürlich oder nach einem Algorithmus ausgewählt werden. Am häufigsten wird die sequentielle Aufzählung vom Anfang des Arrays an verwendet, wo ein geordnetes Segment gebildet wird.
Der Beginn der Sortierung könnte so aussehen:
- Nimm das erste Element des Arrays.
- Da es keinen Vergleich gibt, nimm das Element selbst wie bestelltSequenz.
- Gehe zum zweiten Element.
- Vergleiche es mit dem ersten basierend auf der Sortierregel.
- Ggf. Elemente stellenweise tauschen.
- Nehmen Sie die ersten beiden Elemente als geordnete Folge.
- Gehe zum dritten Element.
- Mit dem zweiten vergleichen, ggf. tauschen.
- Falls der Ersatz erfolgt ist, vergleichen Sie ihn mit dem ersten.
- Drei Elemente als geordnete Folge nehmen.
Und so weiter bis zum Ende des ursprünglichen Arrays.
Real Life Insertion Sort
Zur Verdeutlichung lohnt es sich, ein Beispiel zu geben, wie dieser Sortiermechanismus im Alltag verwendet wird.
Nehmen Sie zum Beispiel eine Brieftasche. Im Geldscheinfach liegen Hundert-, Fünfhundert- und Tausend-Dollar-Scheine durcheinander. Das ist ein Durcheinander, in einem solchen Sammelsurium ist es schwierig, sofort das richtige Stück Papier zu finden. Die Anordnung der Banknoten muss sortiert werden.
Die allererste ist eine Banknote von 1000 Rubel und unmittelbar danach - 100. Wir nehmen 100 und legen sie davor. Der dritte in Folge kostet 500 Rubel, der rechtmäßige Platz dafür liegt zwischen hundert und tausend.
Auf die gleiche Weise sortieren wir die erh altenen Karten beim Spielen des "Narren", um die Navigation zu erleichtern.
Operatoren und Hilfsfunktionen
Die Insertion-Sort-Methode nimmt als Eingabe ein anfängliches zu sortierendes Array, eine Vergleichsfunktion und, falls erforderlich, eine Funktion, die die Regel zum Aufzählen von Elementen festlegt. Meistens stattdessen verwendetreguläre Schleifenanweisung.
Das erste Element ist selbst eine geordnete Menge, also beginnt der Vergleich beim zweiten.
Der Algorithmus verwendet oft eine Hilfsfunktion, um zwei Werte auszutauschen (swap). Es verwendet eine zusätzliche temporäre Variable, die Speicher verbraucht und den Code etwas verlangsamt.
Eine Alternative besteht darin, eine Gruppe von Elementen massenhaft zu verschieben und dann das aktuelle in den freien Raum einzufügen. In diesem Fall erfolgt der Übergang zum nächsten Element, wenn der Vergleich ein positives Ergebnis liefert, was die richtige Reihenfolge anzeigt.
Implementierungsbeispiele
Die konkrete Implementierung hängt stark von der verwendeten Programmiersprache, deren Syntax und Strukturen ab.
Klassische C-Implementierung mit temporärer Variable zum Austausch von Werten:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; Array[j + 1]=Array[j]; array[j]=temp; } }
PHP-Implementierung:
function insert_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Hier werden zunächst alle Elemente, die nicht der Sortierbedingung entsprechen, nach rechts geschoben und dann das aktuelle Element an die freie Stelle eingefügt.
Java-Code mit While-Schleife:
public static void insertSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=aktuelleElement; prevKey--; } } }
Die allgemeine Bedeutung des Codes bleibt unverändert: Jedes Element des Arrays wird sequentiell mit den vorherigen verglichen und ggf. mit ihnen vertauscht.
Geschätzte Laufzeit
Offensichtlich ist die Eingabe des Algorithmus im besten Fall ein bereits richtig geordnetes Array. In dieser Situation muss der Algorithmus einfach jedes Element überprüfen, um sicherzustellen, dass es sich an der richtigen Stelle befindet, ohne einen Austausch vorzunehmen. Somit hängt die Laufzeit direkt von der Länge des ursprünglichen Arrays O(n) ab.
Die Worst-Case-Eingabe ist ein Array, das in umgekehrter Reihenfolge sortiert ist. Dies erfordert eine große Anzahl von Permutationen, die Laufzeitfunktion hängt von der Anzahl der Elemente zum Quadrat ab.
Die genaue Anzahl der Permutationen für ein völlig ungeordnetes Array lässt sich mit folgender Formel berechnen:
n(n-1)/2
wobei n die Länge des ursprünglichen Arrays ist. Somit wären 4950 Permutationen erforderlich, um 100 Elemente in der richtigen Reihenfolge anzuordnen.
Die Einfügemethode ist sehr effizient zum Sortieren kleiner oder teilweise sortierter Arrays. Aufgrund der hohen Komplexität der Berechnungen ist es jedoch nicht empfehlenswert, es überall anzuwenden.
Der Algorithmus wird als Hilfsmittel in vielen anderen komplexeren Sortierverfahren verwendet.
Gleiche Werte sortieren
Der Einfügealgorithmus gehört zu den sogenannten stabilen Sortierungen. Das heisst,dass es identische Elemente nicht vertauscht, sondern ihre ursprüngliche Reihenfolge beibehält. Der Stabilitätsindex ist in vielen Fällen wichtig für die richtige Bestellung.
Das Obige ist ein großartiges visuelles Beispiel für Insertion Sort in einem Tanz.
