Meilleure réponse
Tout dabord, il faut se demander pourquoi utiliser un algorithme de tri quadratique alors que des alternatives asymptotiquement plus rapides existent, comme le tri par fusion ou tri rapide. Pour les petits tableaux (moins de 20 à 30 éléments), le tri par insertion et le tri par sélection sont généralement plus rapides que les alternatives O (n * logn). En fait, de nombreux algorithmes de tri basés sur le paradigme diviser et conquérir passent au tri par insertion ou au tri par sélection lorsque le tableau est suffisamment petit.
Entre le tri par insertion et le tri par sélection, quand utiliser lequel?
En général, le tri par insertion effectuera moins de comparaisons que le tri par sélection, en fonction du degré de « tri » du tableau. Alors que le tri par sélection doit analyser les parties restantes du tableau lors du placement dun élément, le tri par insertion analyse uniquement autant déléments que nécessaire. Cela signifie que lorsque le tableau est déjà trié ou presque trié, le tri par insertion seffectue en temps O (n).
Un avantage du tri par sélection par rapport au tri par insertion, est que le nombre décritures (swaps) est compris dans O (n), tandis quen tri par insertion, il est en O (n ^ 2). Cela peut être important si vous effectuez un tri sur mémoire Flash, par exemple, car les écritures réduisent la durée de vie de la mémoire Flash.
Réponse
Dans un tri par sélection, pour chaque élément à être ajouté à la section triée, vous devez parcourir la partie non triée entière de la liste pour trouver lélément minimal restant. Dans un tri par insertion, vous devez rechercher la section triée pour savoir où va lélément suivant mais la recherche se termine une fois que vous avez trouvé le point dinsertion (environ la moitié
Le tri par sélection nécessite donc N / 2 comparaisons en moyenne pour chaque élément à ajouter à la section triée et le tri par insertion nécessite N / 4 comparaisons en moyenne. Cependant, le tri par insertion a une pénalité de temps supplémentaire lors du tri dun tableau. Chacune des comparaisons N / 4 (en moyenne) nécessite que lélément soit déplacé vers le haut, il y a donc également N / 4 mouvements ainsi que des comparaisons. Le tri par sélection ne nécessite quun seul échange.
Dans lensemble, le tri par insertion remporte généralement la course. Cela est particulièrement vrai sil existe des fonctions rapides de «déplacement de bloc» (pour les tableaux).