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.
InformationsquelleAutor | 2009-04-10