Disons que j'ai une liste d'objets triés par un champ spécifique sur cet objet. Si l'un des objets change de propriété, sa position dans la liste triée devrait être mise à jour.
Qu'est-ce que l'algorithme de tri ou des "astuces" pourrais-je utiliser pour trier très rapidement cette liste, étant donné qu'il n'arrête de trier qu'un seul élément à la fois?
La structure de données est une matrice et j'ai un accès direct à l'index de l'élément modifié.
J'utilise Scala pour cela, mais tous les conseils généraux ou les pointeurs seraient également utiles.
7 Réponses :
Vous pouvez simplement faire une itération de tri de bulle: Démarrer depuis le début de la liste et itérer jusqu'à ce que vous trouviez l'élément hors commandement. Puis déplacez-le dans la direction appropriée jusqu'à ce qu'il tombe en place. Cela vous donnera au pire des performances 2n.
Déplacement de l'élément non formé à gauche ou à droite dans la liste semble la solution optimale
Pourriez-vous expliquer cela plus loin?
En supposant que vous sachiez où votre nouvel élément est, vous avez une liste triée: 1 2 3 4 5 6 9 Une fois que le nouvel élément a été ajouté: 1 2 3 4 x 5 6 9 Maintenant - si x est supérieur à 5, vous pouvez déplacer x à droite par inverse x et 5 et répéter avec l'élément suivant à droite jusqu'à ce que je ne puisse pas faire le même déplacement X à gauche
Si la liste est triée, vous pouvez simplement supprimer l'élément sur lequel vous serez sur le point de passer de la liste et, après le changer, vous pourriez "insert binaire", non? Cela prendrait une moyenne des étapes de journal (n).
Si vous le pouvez, changez d'un tableau en java.util.Tremap: la suppression et l'insertion seront des opérations de journalisation (n): qui seront plus rapides que votre insertion d'accès + O (n). solution à l'aide d'un tableau.
Cela semble énormément mieux qu'une approche à bulles, qui serait linéaire à temps. +1
Cela nécessite un accès aléatoire au tableau et O (1) insertion. Ne fonctionnera pas non plus sur des listes liées ni des tableaux.
Si la liste est une liste liée ou une bête similaire, c'est probablement la meilleure option, mais si les données sont dans un tableau, cela ne sera pas meilleur que la version de tri de la bulle, car le même nombre d'éléments devra être déplacé.
Tirpen, vous ne pouvez pas effectuer une recherche binaire sur une liste que vous ne pouvez pas indexer, les listes ainsi liées sont hors de question.
Soit j'ai manqué la partie array, ou le message a été édité, mais oui, SDCVVC et Joren ont raison: cela ne fonctionnera pas en cas de matrice ou de liste liée. Comme Scala est la langue, je dirais aller pour un Treemap. La récupération ne sera plus O (1), mais la suppression et l'insertion seront toutes deux des opérations de log (n).
Supprimez le seul élément et reformez-l'ajouter dans la position correcte. si vous faites seulement un élément, votre temps d'exécution maximum est n.
Si vous faites plus d'un, vous devriez attendre qu'ils soient tous terminés, puis complexes. Mais vous devrez nous en dire beaucoup plus sur votre espace problématique. Rapide est contraind par la mémoire et d'autres facteurs que vous devez déterminer pour choisir l'algorithme droit.
Selon si la nouvelle valeur est supérieure supérieure à ou inférieure à celle du précédent, vous pouvez "buller" en place.
Le pseudo-code ressemblerait à ceci: P>
a b c d e g h i f j 10 20 30 40 50 70 80 90 95 100
Si la liste est vraiment grande et que vous avez un grand nombre d'opérations de mise à jour attendues, une simple liste d'accès aléatoire ou une liste liée au randonneur sera trop lente. Si vous utilisez des tableaux / listes liées, chaque opération de mise à jour coûtera O (n). Avec de petites listes et / ou un petit nombre de mises à jour, cela est adéquat.
Pour les listes plus importantes, vous pouvez obtenir des mises à jour O (n)) à l'aide d'une structure de données O (journal (n) (n)) (AVL / RB, saut-listes, des arbres de segment, etc.). Une implémentation simple peut impliquer de supprimer l'élément à mettre à jour, de modifier la valeur, puis de la réinsérer. De nombreuses langues populaires ont une sorte de structure de données triée dans leur bibliothèque (E.G. Treemap / Arbreset en Java, Multiset / Multimap en C ++ 'S STL), ou vous pouvez facilement trouver une implémentation gratuite pour votre langue.
Pour un tableau, l'insertion d'un élément dans la position correcte serait O (n), car vous devez copier les éléments de matrice pour faire de la place pour un élément supplémentaire. Vous pouvez trouver l'index dont vous avez besoin pour insérer en effectuant un Recherche binaire (O (log n )) ou Recherche linéaire (O (n)). Quel que soit le choix que vous faites, l'algorithme dans son ensemble sera O (n).
Le seul moyen de faire cela O (log n) est
La réponse dépend de la manière dont la liste est représentée (liste liée, tableau) et si vous avez ou non un accès direct à l'élément modifié ou devez le trouver en premier. Comme indiqué, cette question est sous-spécifiée.