¿Manera eficiente de insertar un número en un conjunto ordenado de números?

Tengo una matriz de JavaScript ordenada y deseo insertar un elemento más en la matriz, de modo que la matriz resultante permanezca ordenada. Ciertamente podría implementar una simple función de inserción de estilo de clasificación rápida:

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));

[ADVERTENCIA] este código tiene un error al intentar insertarlo al comienzo de la matriz, por ejemplo insert(2, [3, 7 ,9]) produce incorrectos [3, 2, 7, 9].

Sin embargo, noté que las implementaciones de la función Array.sort podrían hacer esto por mí y de forma nativa:

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));

¿Hay una buena razón para elegir la primera implementación sobre la segunda?

Editar : Tenga en cuenta que para el caso general, una inserción de O (log (n)) (como se implementó en el primer ejemplo) será más rápida que un algoritmo de clasificación genérico; sin embargo, este no es necesariamente el caso de JavaScript en particular. Tenga en cuenta que:

• El mejor caso para varios algoritmos de inserción es O (n), que sigue siendo significativamente diferente de O (log (n)), pero no tan malo como O (n log (n)) como se menciona a continuación. Se reduciría al algoritmo de clasificación particular utilizado (ver implementación de Javascript Array.sort? )
• El método de clasificación en JavaScript es una función nativa, por lo que puede obtener enormes beneficios: O (log (n)) con un coeficiente enorme puede ser mucho peor que O (n) para conjuntos de datos de tamaño razonable.

Solo como un único punto de datos, para las patadas probé esto insertando 1000 elementos aleatorios en una matriz de 100,000 números ordenados previamente usando los dos métodos que usan Chrome en Windows 7:

First Method:
~54 milliseconds
Second Method:
~57 seconds

Entonces, al menos en esta configuración, el método nativo no lo compensa. Esto es cierto incluso para pequeños conjuntos de datos, insertando 100 elementos en una matriz de 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

Simple ( Demo ):

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

Muy buena y notable pregunta con una discusión muy interesante! También estaba usando elArray.sort() función después de empujar un solo elemento en una matriz con algunos miles de objetos.

Tuve que extender su locationOffunción para mi propósito debido a que tenía objetos complejos y, por lo tanto, la necesidad de una función de comparación como en Array.sort():

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};

Hay un error en tu código. Debería leer:

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

Sin esta solución, el código nunca podrá insertar un elemento al comienzo de la matriz.

Sé que esta es una vieja pregunta que ya tiene una respuesta, y hay varias otras respuestas decentes. Veo algunas respuestas que proponen que puede resolver este problema buscando el índice de inserción correcto en O (log n); puede, pero no puede insertar en ese momento, porque la matriz debe copiarse parcialmente para hacer espacio.

En pocas palabras: si realmente necesita O (log n) inserta y elimina en una matriz ordenada, necesita una estructura de datos diferente, no una matriz. Deberías usar un B-Tree . Las ganancias de rendimiento que obtendrá al usar un B-Tree para un conjunto de datos grande, eclipsarán cualquiera de las mejoras que se ofrecen aquí.

Si debe usar una matriz. Ofrezco el siguiente código, basado en el tipo de inserción, que funciona, si y solo si la matriz ya está ordenada. Esto es útil para el caso cuando necesita recurrir después de cada inserción:

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

Debería funcionar en O (n), que creo que es lo mejor que puedes hacer. Sería mejor si js admitiera la asignación múltiple. Aquí hay un ejemplo para jugar:

Actualizar:

esto podría ser más rápido:

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

Enlace JS Bin actualizado

Su función de inserción supone que la matriz dada está ordenada, busca directamente la ubicación donde se puede insertar el nuevo elemento, generalmente simplemente mirando algunos de los elementos en la matriz.

La función de clasificación general de una matriz no puede tomar estos atajos. Obviamente, al menos tiene que inspeccionar todos los elementos de la matriz para ver si ya están ordenados correctamente. Este hecho por sí solo hace que la ordenación general sea más lenta que la función de inserción.

Un algoritmo de ordenación genérico generalmente es O (n ⋅ log (n)) en promedio y, dependiendo de la implementación, podría ser el peor de los casos si la matriz ya está ordenada, lo que lleva a complejidades de O (n ² ) . La búsqueda directa de la posición de inserción tiene una complejidad de O (log (n)) , por lo que siempre será mucho más rápido.

Para una pequeña cantidad de artículos, la diferencia es bastante trivial. Sin embargo, si está insertando una gran cantidad de elementos o trabajando con una matriz muy grande, llamar a .sort () después de cada inserción causará una gran cantidad de sobrecarga.

Terminé escribiendo una función de búsqueda / inserción binaria bastante hábil para este propósito exacto, así que pensé en compartirla. Dado que utiliza un whilebucle en lugar de recurrencia, no se escuchan llamadas de funciones adicionales, por lo que creo que el rendimiento será incluso mejor que cualquiera de los métodos publicados originalmente. Y emula el Array.sort()comparador predeterminado de forma predeterminada, pero acepta una función de comparación personalizada si lo desea.

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

Si está abierto a usar otras bibliotecas, lodash proporciona las funciones sortedIndex y sortedLastIndex , que podrían usarse en lugar del whilebucle. Las dos desventajas potenciales son 1) el rendimiento no es tan bueno como mi método (aunque no estoy seguro de cuánto peor es) y 2) no acepta una función de comparación personalizada, solo un método para obtener el valor para comparar (usando el comparador predeterminado, supongo).

Aquí hay algunos pensamientos: en primer lugar, si está realmente preocupado por el tiempo de ejecución de su código, ¡asegúrese de saber qué sucede cuando llama a las funciones integradas! No sé desde arriba en JavaScript, pero un rápido google de la función de empalme devolvió esto , lo que parece indicar que estás creando una matriz completamente nueva en cada llamada. No sé si realmente importa, pero ciertamente está relacionado con la eficiencia. Veo que Breton, en los comentarios, ya lo ha señalado, pero ciertamente cumple con cualquier función de manipulación de matriz que elija.

De todos modos, en realidad resolviendo el problema.

Cuando leí que querías ordenar, ¡mi primer pensamiento es usar el método de inserción! . Es útil porque se ejecuta en tiempo lineal en listas ordenadas o casi ordenadas . Como sus matrices tendrán solo 1 elemento fuera de orden, eso cuenta como casi ordenado (excepto, bueno, matrices de tamaño 2 o 3 o lo que sea, pero en ese punto, vamos). Ahora, implementar el tipo no es tan malo, pero es una molestia con la que no querrás lidiar, y de nuevo, no sé nada sobre JavaScript y si será fácil o difícil o no. Esto elimina la necesidad de su función de búsqueda, y simplemente presiona (como Breton sugirió).

En segundo lugar, su función de búsqueda "quicksort-esque" parece ser un algoritmo de búsqueda binaria . Es un algoritmo muy agradable, intuitivo y rápido, pero con un inconveniente: es muy difícil de implementar correctamente. No me atreveré a decir si el tuyo es correcto o no (¡espero que lo sea, por supuesto! :)), pero ten cuidado si quieres usarlo.

De todos modos, resumen: el uso de "push" con clasificación de inserción funcionará en tiempo lineal (suponiendo que el resto de la matriz esté ordenado) y evitará cualquier requisito de algoritmo de búsqueda binaria desordenado. No sé si esta es la mejor manera (implementación subyacente de matrices, tal vez una función incorporada loca lo hace mejor, quién sabe), pero me parece razonable. :) - Agor.

Aquí hay una comparación de cuatro algoritmos diferentes para lograr esto: https://jsperf.com/sorted-array-insert-comparison/1

Algoritmos

• Ingenuo: simplemente presione y clasifique () después
• Lineal: iterar sobre la matriz e insertar donde sea apropiado
• Búsqueda binaria: tomada de https://stackoverflow.com/a/20352387/154329
• "Quick Sort Like": la solución refinada de sintético cero ( https://stackoverflow.com/a/18341744/154329 )

La ingenuidad siempre es horrible. Parece que para tamaños de matriz pequeños, los otros tres no difieren demasiado, pero para matrices más grandes, los últimos 2 superan el enfoque lineal simple.

Aquí hay una versión que usa lodash.

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

nota: sortedIndex realiza una búsqueda binaria.

La mejor estructura de datos que se me ocurre es una lista de salto indexada que mantiene las propiedades de inserción de las listas vinculadas con una estructura jerárquica que permite las operaciones de tiempo de registro. En promedio, las búsquedas, la inserción y las búsquedas de acceso aleatorio se pueden realizar en tiempo O (log n).

Un árbol de estadísticas de orden permite la indexación del tiempo de registro con una función de clasificación.

Si no necesita acceso aleatorio pero necesita la inserción O (log n) y la búsqueda de claves, puede deshacerse de la estructura de la matriz y usar cualquier tipo de árbol de búsqueda binario .

Ninguna de las respuestas que usa array.splice()son eficientes en absoluto, ya que eso es en promedio el tiempo O (n).¿Cuál es la complejidad temporal de array.splice () en Google Chrome?

Aquí está mi función, usa la búsqueda binaria para encontrar el elemento y luego la inserta de manera apropiada:

function binaryInsert(val, arr){
    let mid, 
    len=arr.length,
    start=0,
    end=len-1;
    while(start <= end){
        mid = Math.floor((end + start)/2);
        if(val <= arr[mid]){
            if(val >= arr[mid-1]){
                arr.splice(mid,0,val);
                break;
            }
            end = mid-1;
        }else{
            if(val <= arr[mid+1]){
                arr.splice(mid+1,0,val);
                break;
            }
            start = mid+1;
        }
    }
    return arr;
}

console.log(binaryInsert(16, [
    5,   6,  14,  19, 23, 44,
   35,  51,  86,  68, 63, 71,
   87, 117
 ]));

No vuelva a ordenar después de cada artículo, es excesivo ...

Si solo hay un elemento para insertar, puede encontrar la ubicación para insertar mediante la búsqueda binaria. Luego use memcpy o similar para copiar en masa los elementos restantes para hacer espacio para el insertado. La búsqueda binaria es O (log n), y la copia es O (n), dando O (n + log n) total. Usando los métodos anteriores, está haciendo una reordenación después de cada inserción, que es O (n log n).

¿Importa? Digamos que está insertando aleatoriamente k elementos, donde k = 1000. La lista ordenada es de 5000 elementos.

• Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
• Re-sort on each = k*(n log n) = ~60 million ops

Si los k elementos para insertar llegan cada vez, entonces debe hacer buscar + mover. Sin embargo, si se le proporciona una lista de k elementos para insertar en una matriz ordenada, con anticipación, puede hacerlo aún mejor. Ordene los k elementos, por separado de la matriz n ya ordenada. Luego, haga una ordenación de exploración, en la que mueve hacia abajo ambas matrices ordenadas simultáneamente, fusionando una en la otra. - Clasificación de fusión en un paso = k log k + n = 9965 + 5000 = ~ 15,000 operaciones

Actualización: con respecto a su pregunta.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n)Explica exactamente los tiempos que está recibiendo.

function insertOrdered(array, elem) {
    let _array = array;
    let i = 0;
    while ( i < array.length && array[i] < elem ) {i ++};
    _array.splice(i, 0, elem);
    return _array;
}