Einfügesortierung in JavaScript
In diesem Artikel wird die Idee der Insertion Sort in JavaScript erörtert und ein Beispiel für ihre Implementierung bereitgestellt.
Sortiertechniken in JavaScript
Eine ganze Reihe von Sortiertechniken wurde von interessierten Personen mit der Vision entwickelt, Optimalität, Beschleunigung und weniger Abstände zu gewährleisten. In diesem Durchlauf zeigt die Einfügungssortierung, dass die zeitliche Komplexität im ungünstigsten Fall O(n^2) ist, während der beste Fall O(n) ist.
Für eine kleine zu sortierende Datenmenge ist Array.prototype.sort() eine gute Wahl. Als bevorzugte Situation ergibt sich eine Zeitkomplexität von O(n), was besser ist als O(n*logn).
Die Funktion sort() funktioniert jedoch nicht gut für einen riesigen Datenhaufen mit komplexen Objekten usw. Die Funktion Array.prototype.sort() hat die Implementierung der Einfügungssortierung und damit des JavaScript-Standardsortieralgorithmus ist nicht in der effizienten Kategorie.
Es sollte auch beachtet werden, dass die Leistung beim Sortieren eines Codes davon abhängt, welchen Browser der Benutzer verwendet. Chrome V8 verwendet Tim Sort (Insertion Sort + Merge Sort), und Firefox verwendet das grundlegende Merge Sort.
Im realen Szenario sind Rohdaten nicht unbedingt unsortiert. Stattdessen folgen sie einem Ordnungsmuster. Man kann also sagen, dass die Daten nicht von Grund auf neu sortiert werden müssen.
Beim V8 wird das Array zunächst in Blöcke unterteilt, die als run bezeichnet werden. Diese runs in der untersten Ebene werden nach dem Insertion-Sort-Prinzip sortiert und später nach dem Merge-Sort-Prinzip zusammengeführt.
Wenn Sie mit wenigen Zahlen oder Objekten arbeiten, verhält sich die Tim-Sortierung wie eine Insertion-Sortierung mit einer Zeitkomplexität von O(n). Bei großen Datenmengen hingegen arbeitet V8 Sort als Merge Sort mit der Zeitkomplexität O(n*logn).
Tim Sort ist also eine hochgradig optimierte, stabilere Sortiertechnik als die traditionelle Merge Sort.
In unserem Beispielabschnitt behandeln wir die Grundidee einer Insertion Sort und lassen Sie feststellen, warum sie ihre Einschränkungen hat und warum sie besser sein könnte als viele andere. Die Diskussion aus dem vorherigen Abschnitt beschreibt, wie die Einfügungssortierung in der V8-Engine verwendet wird, da es sich um eine JavaScript-Engine handelt.
Kommen wir zur Demonstration.
Implementieren Sie die Insertion Sort-Technik in JavaScript
Die Grundidee dieses Sortierens kann mit dem Sortieren eines Kartenblattes verglichen werden. Wir legen zunächst eine Karte als erste fest und wählen später die nächsten zu sortierenden Karten aus, die als erste festgelegte Karte bezeichnet werden.
Hier wird die nächste Karte als Schlüssel bezeichnet, und wenn der Schlüssel größer als die erste Karte ist, dann behalten wir es so wie es ist; Andernfalls vertauschen wir die Position des Schlüssels und der ersten Karte. Und dies wiederholt sich, bis das gesamte Array durchlaufen und sortiert ist.
Lassen Sie uns die Codezeilen überprüfen.
Code-Auszug:
var arr = [4, 2, 3, 1, 7];
var size = arr.length;
for (var i = 1; i < size; i++) {
var key = arr[i];
var j = i - 1;
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
console.log(arr)
Ausgang:
Wie wir sehen können, hat die Insertion Sort eine Platzkomplexität von O(1), da sie kein anderes Array von Plätzen belegt, um den Schlüssel zu speichern, als den Slot 1. Wenn Sie also auf optimalen Platz achten, könnte diese Sorte gut passen.
