Un moyen efficace d'insérer un nombre dans un tableau trié de nombres?

J'ai un tableau JavaScript trié et je souhaite insérer un autre élément dans le tableau afin que le tableau résultant reste trié. Je pourrais certainement implémenter une simple fonction d'insertion de type tri rapide:

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

[AVERTISSEMENT] ce code a un bogue en essayant d'insérer au début du tableau, par exemple insert(2, [3, 7 ,9]) produit incorrect [3, 2, 7, 9].

Cependant, j'ai remarqué que les implémentations de la fonction Array.sort pourraient potentiellement le faire pour moi, et de manière native:

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

Y a-t-il une bonne raison de choisir la première implémentation plutôt que la seconde?

Edit : Notez que pour le cas général, une insertion O (log (n)) (telle qu'implémentée dans le premier exemple) sera plus rapide qu'un algorithme de tri générique; cependant ce n'est pas nécessairement le cas pour JavaScript en particulier. Notez que:

• Le meilleur cas pour plusieurs algorithmes d'insertion est O (n), qui est toujours significativement différent de O (log (n)), mais pas aussi mauvais que O (n log (n)) comme mentionné ci-dessous. Cela reviendrait à l'algorithme de tri particulier utilisé (voir l' implémentation Javascript Array.sort? )
• La méthode de tri en JavaScript est une fonction native, donc potentiellement réaliser d'énormes avantages - O (log (n)) avec un coefficient énorme peut encore être bien pire que O (n) pour des ensembles de données de taille raisonnable.

Tout comme un point de données unique, pour les coups de pied, j'ai testé cela en insérant 1000 éléments aléatoires dans un tableau de 100000 nombres pré-triés en utilisant les deux méthodes utilisant Chrome sur Windows 7:

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

Donc, au moins sur cette configuration, la méthode native ne compense pas cela. Cela est vrai même pour les petits ensembles de données, en insérant 100 éléments dans un tableau de 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

Simple ( démo ):

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

Très bonne et remarquable question avec une discussion très intéressante! J'utilisais également la Array.sort()fonction après avoir poussé un seul élément dans un tableau avec quelques milliers d'objets.

J'ai dû étendre votre locationOffonction pour mon objectif en raison de la complexité des objets et donc du besoin d'une fonction de comparaison comme dans 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;
};

Il y a un bogue dans votre code. Il devrait lire:

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

Sans ce correctif, le code ne pourra jamais insérer un élément au début du tableau.

Je sais que c'est une vieille question qui a déjà une réponse, et il existe un certain nombre d'autres réponses décentes. Je vois quelques réponses qui suggèrent que vous pouvez résoudre ce problème en recherchant le bon index d'insertion dans O (log n) - vous pouvez, mais vous ne pouvez pas insérer dans ce temps, car le tableau doit être partiellement copié pour faire espace.

Bottom line: Si vous avez vraiment besoin d'insertions et de suppressions O (log n) dans un tableau trié, vous avez besoin d'une structure de données différente - pas d'un tableau. Vous devez utiliser un B-Tree . Les gains de performances que vous obtiendrez en utilisant un arbre B pour un grand ensemble de données éclipseront toutes les améliorations proposées ici.

Si vous devez utiliser un tableau. Je propose le code suivant, basé sur le tri par insertion, qui fonctionne, si et seulement si le tableau est déjà trié. Ceci est utile dans le cas où vous devez recourir après chaque insertion:

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

Il devrait fonctionner en O (n), ce que je pense est le mieux que vous puissiez faire. Ce serait mieux si js prenait en charge l'affectation multiple. voici un exemple avec lequel jouer:

Mettre à jour:

cela pourrait être plus rapide:

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

Lien JS Bin mis à jour

Votre fonction d'insertion suppose que le tableau donné est trié, elle recherche directement l'emplacement où le nouvel élément peut être inséré, généralement en regardant simplement quelques-uns des éléments du tableau.

La fonction de tri générale d'un tableau ne peut pas prendre ces raccourcis. De toute évidence, il doit au moins inspecter tous les éléments du tableau pour voir s'ils sont déjà correctement ordonnés. Ce seul fait rend le tri général plus lent que la fonction d'insertion.

Un algorithme de tri générique est généralement en moyenne O (n ⋅ log (n)) et en fonction de l'implémentation, il peut en fait être le pire des cas si le tableau est déjà trié, conduisant à des complexités de O (n ² ) . La recherche directe de la position d'insertion a plutôt une complexité de O (log (n)) , donc ce sera toujours beaucoup plus rapide.

Pour un petit nombre d'articles, la différence est assez insignifiante. Cependant, si vous insérez beaucoup d'éléments ou travaillez avec un très grand tableau, appeler .sort () après chaque insertion entraînera une surcharge considérable.

J'ai fini par écrire une fonction de recherche / insertion binaire assez astucieuse dans ce but précis, alors j'ai pensé la partager. Comme il utilise une whileboucle au lieu de la récursivité, il n'y a pas d'appel de fonction supplémentaire, donc je pense que les performances seront encore meilleures que l'une des méthodes publiées à l'origine. Et il émule le Array.sort()comparateur par défaut par défaut, mais accepte une fonction de comparateur personnalisée si vous le souhaitez.

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 vous êtes prêt à utiliser d'autres bibliothèques, lodash fournit les fonctions sortedIndex et sortedLastIndex , qui peuvent être utilisées à la place de la whileboucle. Les deux inconvénients potentiels sont 1) les performances ne sont pas aussi bonnes que ma méthode (je ne suis pas sûr de savoir à quel point elles sont pires) et 2) elles n'acceptent pas une fonction de comparateur personnalisée, uniquement une méthode pour obtenir la valeur à comparer (en utilisant le comparateur par défaut, je suppose).

Voici quelques réflexions: Premièrement, si vous êtes vraiment préoccupé par l'exécution de votre code, assurez-vous de savoir ce qui se passe lorsque vous appelez les fonctions intégrées! Je ne sais pas de haut en bas en javascript, mais un rapide google de la fonction d'épissure a renvoyé ceci , ce qui semble indiquer que vous créez un tout nouveau tableau à chaque appel! Je ne sais pas si c'est vraiment important, mais c'est certainement lié à l'efficacité. Je vois que Breton, dans les commentaires, l'a déjà souligné, mais cela vaut certainement pour la fonction de manipulation de tableau que vous choisissez.

Quoi qu'il en soit, sur la résolution du problème.

Quand j'ai lu que vous vouliez trier, ma première pensée est d'utiliser le tri par insertion! . Il est pratique car il s'exécute en temps linéaire sur des listes triées ou presque triées . Comme vos tableaux n'auront qu'un seul élément dans le désordre, cela compte comme presque trié (sauf pour les tableaux de taille 2 ou 3 ou autre, mais à ce stade, allez). Maintenant, la mise en œuvre du tri n'est pas trop mauvaise, mais c'est un problème que vous ne voudrez peut-être pas gérer, et encore une fois, je ne sais rien sur javascript et si ce sera facile ou difficile ou autre chose. Cela supprime le besoin de votre fonction de recherche et il vous suffit de pousser (comme le suggère Breton).

Deuxièmement, votre fonction de recherche "quicksort-esque" semble être un algorithme de recherche binaire ! C'est un très bel algorithme, intuitif et rapide, mais avec un hic: il est notoirement difficile à mettre en œuvre correctement. Je n'oserai pas dire si le vôtre est correct ou non (j'espère bien sûr! :)), mais méfiez-vous si vous voulez l'utiliser.

Quoi qu'il en soit, résumé: l'utilisation de "push" avec le tri par insertion fonctionnera en temps linéaire (en supposant que le reste du tableau soit trié), et évite toute exigence d'algorithme de recherche binaire compliquée. Je ne sais pas si c'est le meilleur moyen (implémentation sous-jacente de tableaux, peut-être qu'une fonction intégrée folle le fait mieux, qui sait), mais cela me semble raisonnable. :) - Agor.

Voici une comparaison de quatre algorithmes différents pour y parvenir: https://jsperf.com/sorted-array-insert-comparison/1

Algorithmes

• Naïf: il suffit de pousser et de trier () après
• Linéaire: itérer sur le tableau et insérer le cas échéant
• Recherche binaire: tirée de https://stackoverflow.com/a/20352387/154329
• "Quick Sort Like": la solution raffinée de synthèsezero ( https://stackoverflow.com/a/18341744/154329 )

Naïf est toujours horrible. Il semble que pour les petites tailles de tableaux, les trois autres ne diffèrent pas trop, mais pour les plus grands tableaux, les 2 derniers surpassent l'approche linéaire simple.

Voici une version qui utilise lodash.

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

remarque: sortedIndex effectue une recherche binaire.

La meilleure structure de données à laquelle je puisse penser est une liste de sauts indexée qui conserve les propriétés d'insertion des listes liées avec une structure hiérarchique qui permet les opérations de journalisation. En moyenne, la recherche, l'insertion et les recherches d'accès aléatoire peuvent être effectuées en temps O (log n).

Un arbre statistique d'ordre permet l'indexation de l'heure du journal avec une fonction de classement.

Si vous n'avez pas besoin d'un accès aléatoire mais que vous avez besoin de l'insertion O (log n) et de la recherche de clés, vous pouvez abandonner la structure du tableau et utiliser n'importe quel type d' arbre de recherche binaire .

Aucune des réponses utilisées array.splice()n'est efficace du tout puisque c'est en moyenne O (n) temps. Quelle est la complexité temporelle de array.splice () dans Google Chrome?

Voici ma fonction, utilise la recherche binaire pour trouver un élément, puis insère de manière appropriée:

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

Ne pas trier à nouveau après chaque élément, c'est exagéré.

S'il n'y a qu'un seul élément à insérer, vous pouvez trouver l'emplacement à insérer à l'aide de la recherche binaire. Ensuite, utilisez memcpy ou similaire pour copier en bloc les éléments restants pour faire de la place pour celui inséré. La recherche binaire est O (log n), et la copie est O (n), ce qui donne le total O (n + log n). En utilisant les méthodes ci-dessus, vous effectuez un nouveau tri après chaque insertion, qui est O (n log n).

Est-ce que ça importe? Disons que vous insérez aléatoirement k éléments, où k = 1000. La liste triée est de 5000 éléments.

• 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 les k éléments à insérer arrivent à chaque fois, vous devez effectuer une recherche + un déplacement. Cependant, si vous recevez une liste de k éléments à insérer dans un tableau trié - à l'avance - vous pouvez faire encore mieux. Triez les k éléments, séparément du tableau n déjà trié. Ensuite, effectuez un tri par balayage, dans lequel vous descendez simultanément les deux tableaux triés, en fusionnant l'un dans l'autre. - Tri par fusion en une étape = k log k + n = 9965 + 5000 = ~ 15000 opérations

Mise à jour: concernant votre question.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n)Explique exactement les horaires que vous obtenez.

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