Dieser Artikel ist Teil einer Reihe über Sortieralgorithmen in JavaScript. Den Rest der Serie finden Sie hier. Wenn Sie mit Sortieralgorithmen oder Algorithmen im Allgemeinen noch nicht vertraut sind, lesen Sie dies zuerst, um eine solide Grundlage für das weitere Vorgehen zu erhalten. Heute werde ich die Ins und Outs dieser Art abdecken. Die Einfügesortierung ist komplexer, aber etwas nützlicher als die Blasensortierung. Das Worst-Case-Szenario ähnelt dem von Bubble Sort, eignet sich jedoch im besten Fall für Zeiten, in denen Sie ziemlich sicher sind, dass eine Liste sortiert ist oder wahrscheinlich bereits sortiert ist. Lassen Sie uns das große Bild bekommen.
Die Einfügesortierung funktioniert, indem jedes Element innerhalb einer Liste (beginnend mit dem zweiten Element) betrachtet und mit dem vorherigen Element verglichen wird. Wenn das Element zuvor größer ist, werden sie ausgetauscht. Dies wird fortgesetzt, bis das Element kleiner ist, an welchem Punkt wir dasselbe für das nächste Element in der Liste tun.
Einfügesortierung ist gar nicht so schlecht.. solange Sie es unter den richtigen Umständen verwenden.
- Es ist schneller als die meisten O (n log n) Sortieralgorithmen für kleine Listen.
- Es ist extrem speichereffizient und benötigt nur O (1) zusätzlichen Speicherplatz für das einzelne Element, das verschoben wird.
- Es ist stabil – gleiche Elemente erscheinen in der gleichen Reihenfolge in der sortierten Liste.
- Es ist adaptiv — es ist schnell beim Sortieren von meist sortierten Listen oder beim Hinzufügen von Elementen zu einer bereits sortierten Liste.
- Es ist sehr einfach zu implementieren!
Komplexität
Die zeitliche Komplexität dieses Algorithmus ist im schlimmsten Fall quadratisch — O(n2). Wenn sich n der Unendlichkeit nähert, nähert sich der Durchschnittsfall dem schlimmsten Fall geteilt durch zwei. Wenn Ihre Liste jedoch sortiert ist oder fast so, kann sie im besten Fall O (n) sein und somit gut an dieses Szenario angepasst sein.
Wenn es schnell ist
Wie oben erwähnt, kann es unter bestimmten Umständen schnell sein. Betrachten wir das Array, wenn wir einen Algorithmus wie merge sort verwenden, müssten wir immer noch alle Elemente aufteilen und sie dann wieder zusammenführen. Mit der Einfügesortierung müssen wir nur überprüfen, ob sie in der richtigen Reihenfolge ‚bisher sortiert‘ sind, dann verschieben wir alle um einen Index für 1.
Da die Einfügesortierung eine adaptive Sortierung ist, ist sie auch ein ‚Online-Algorithmus‘, was bedeutet, dass wir mit dem Sortieren beginnen können, bevor wir alle Elemente erhalten, und dann die Listen zusammenführen können, sobald die Teilsortierung abgeschlossen ist.
Pseudocode
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Code
Als nächstes? Sortierung zusammenführen. Einer der heute am häufigsten verwendeten Sortieralgorithmen in Browsern.
