Est-il toujours une bonne raison pour utiliser le Tri par Insertion?
Pour usage général, le tri, la réponse semble être non, comme le tri rapide, fusion de tri et de tas de tri ont tendance à mieux performer dans la moyenne - et les pires scénarios. Cependant, le tri par insertion semble exceller dans différentiels de tri, qui est, d'ajouter des éléments à une liste un à un sur une longue période de temps tout en gardant la liste triée, surtout si l'insertion, le tri est mis en œuvre comme une liste chaînée (O(log n) en moyenne cas vs O(n)). Cependant, un tas semble être en mesure d'effectuer tout (ou presque) et de l'accroissement de tri (ajout ou suppression d'un élément unique à partir d'un tas est un scénario du pire cas en O(log n)). Donc exactement ce que fait le tri par insertion ont à offrir sur d'autres comparaison algorithmes de tri ou des tas?
- Si vous chargez une grande quantité de données à partir d'un ralentissement relatif de source externe comme un disque dur, il est souvent préférable d'utiliser une sorte-que-vous-allez algorithme à faire usage de la perte de cycles impliqué dans un CPU d'attente pour le lecteur de se rattraper. Voir ma réponse ci-dessous.
Vous devez vous connecter pour publier un commentaire.
De http://www.sorting-algorithms.com/insertion-sort:
Un concept important dans l'analyse d'algorithmes est asymptotique analyse. Dans le cas de deux algorithmes différents asymptotique temps de course, comme un O(n^2) et un O(nlogn) comme c'est le cas avec le tri par insertion et quicksort respectivement, il n'est pas certain que l'un est plus rapide que l'autre.
La distinction importante avec ce type d'analyse est que, pour N assez grand, un algorithme plus rapide que l'autre. Lors de l'analyse d'un algorithme vers le bas pour un terme comme O(nlogn), vous déposez des constantes. Lorsque réaliste de l'analyse de l'exécution d'un algorithme, ces constantes seront importantes que pour les situations de petit n.
Alors qu'est-ce que cela signifie? Cela signifie que pour certains petits n, certains algorithmes sont plus rapides. Cette l'article de EmbeddedGurus.net comprend un point de vue intéressant sur le choix de différents algorithmes de tri dans le cas d'un espace limité (16k) et de la mémoire limitée du système. Bien sûr, l'article se réfère uniquement tri d'une liste de 20 entiers, de sorte que les grandes commandes de n n'est pas pertinente. Plus courte de code et moins de consommation de mémoire (ainsi que d'éviter une récursion) ont été finalement plus importantes décisions.
Le tri par Insertion a une faible surcharge, il peut être écrit assez succinctement, et il a plusieurs deux avantages principaux: il est stable, et il est assez rapide d'exécution cas lorsque l'entrée est presque triées.
Oui, il y a une raison pour utiliser un tri d'insertion ou de l'une de ses variantes.
Le tri des alternatives (tri rapide, etc.) d'autres réponses ici faire l'hypothèse que les données sont déjà dans la mémoire et prêt à aller.
Mais si vous tentez de lire une grande quantité de données à partir d'un ralentissement de la source externe (un lecteur de disque dur), il y a une grande quantité de temps perdu que le goulot d'étranglement est clairement le canal de données ou le disque lui-même. Il juste ne peut pas tenir avec le CPU. Une série naturelle de attend de se produire durant toute la lecture. Ces attentes sont gaspillage de cycles CPU à moins que vous les utilisez pour sorte que vous allez.
Par exemple, si vous effectuez votre solution à ce être la suivante:
Vous serait très probablement prendre plus de temps que si vous avez de la suite dans deux threads.
Thread:
Thread B:
...ci-dessus vous permet de l'utiliser dans le cas contraire, les pertes de temps. Remarque: le Fil B n'empêche pas de Thread du progrès.
Par le temps, les données sont entièrement lu, il aura été triés et prêt à l'emploi.
La plupart des procédures de tri utilisera quicksort et puis le tri par insertion pour les très petits ensembles de données.
Si vous parlez le maintien d'une liste triée, il n'y a aucun avantage par rapport à un certain type d'arbre, c'est juste plus lent.
Bien, peut-être qu'il consomme moins de mémoire ou de est plus simple de mise en œuvre.
De l'insertion dans une liste triée impliquera une analyse, ce qui signifie que chaque insert est en O(n), donc le tri de n éléments devient O(n^2)
De l'insérer dans un conteneur tel qu'un équilibre de l'arbre, est généralement log(n), donc le tri est O(n log(n)) qui est plus sûr.
Mais pour les petites listes, il ne fait guère de différence. Vous pouvez utiliser un insert de tri si vous devez écrire vous-même, sans bibliothèques, les listes sont de petite taille et/ou vous n'avez pas de soins sur la performance.
OUI,
Le tri par Insertion est mieux que le Tri Rapide sur de courtes listes.
En fait une optimale Tri Rapide a un seuil de taille qu'il s'arrête, et puis tout le tableau est trié par insertion tri-dessus du seuil de limites.
Aussi...
Pour le maintien d'un tableau de bord, le Binaire, le Tri par Insertion peut être aussi bon qu'il obtient.
Voir cette page.
Pour les petits tableaux de tri d'insertion effectue plus rapidement que quicksort.
Java 7 et Java 8 utilise double pivot quicksort pour trier les types de données primitifs.
Double pivot quicksort surpasse typique de pivot unique de quicksort. Selon l'algorithme de double pivot quicksort :
Définitivement insertion le tri effectue quicksort pour les petits tableaux, et c'est pourquoi vous êtes interrupteur pour le tri par insertion pour des tableaux d'une longueur de moins de 27. La raison peut être il n'y a pas récurrences dans le tri par insertion.
Source: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf