Effiziente Möglichkeit, eine Zahl in ein sortiertes Zahlenfeld einzufügen?
Ich habe ein sortiertes JavaScript-Array und möchte ein weiteres Element in das Array einfügen, sodass das resultierende Array sortiert bleibt. Ich könnte sicherlich eine einfache QuickSort-artige Einfügefunktion implementieren:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.splice(locationOf(element, array) + 1, 0, element);
return array;
}
function locationOf(element, array, start, end) {
start = start || 0;
end = end || array.length;
var pivot = parseInt(start + (end - start) / 2, 10);
if (end-start <= 1 || array[pivot] === element) return pivot;
if (array[pivot] < element) {
return locationOf(element, array, pivot, end);
} else {
return locationOf(element, array, start, pivot);
}
}
console.log(insert(element, array));
[WARNUNG] Dieser Code weist einen Fehler auf, wenn versucht wird, an den Anfang des Arrays einzufügen, z.insert(2, [3, 7 ,9]
) erzeugt falsche [3, 2, 7, 9].
Mir ist jedoch aufgefallen, dass Implementierungen der Array.sort-Funktion dies möglicherweise für mich tun können.
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.push(element);
array.sort(function(a, b) {
return a - b;
});
return array;
}
console.log(insert(element, array));
Gibt es einen guten Grund, die erste Implementierung der zweiten vorzuziehen?
Bearbeiten: Beachten Sie, dass für den allgemeinen Fall eine Einfügung von O (log (n)) (wie im ersten Beispiel implementiert) schneller ist als ein generischer Sortieralgorithmus. Dies ist jedoch nicht unbedingt der Fall, insbesondere für JavaScript. Beachten Sie, dass:
Der beste Fall für mehrere Einfügealgorithmen ist O (n), das sich immer noch erheblich von O (log (n)) unterscheidet, aber nicht ganz so schlecht ist wie O (n log (n)), wie unten erwähnt. Es käme auf den jeweils verwendeten Sortieralgorithmus an (vglJavascript Array.sort Implementierung?)Die Sortiermethode in JavaScript ist eine systemeigene Funktion, daher kann die Realisierung von enormen Vorteilen - O (log (n)) mit einem enormen Koeffizienten - für Datensätze mit angemessener Größe noch viel schlechter als O (n) sein.