Algorithmes quadratiques

On peut se demander pourquoi utiliser un algorithme de tri quadratique alors qu'il en existe de plus performants. La réponse est que la complexité des algorithmes de tri concerne le pire des cas et que certains de ces algorithmes sont performants dans des cas spécifiques. De plus, certains algorithmes quadratiques sont plus performants sur de petites quantités de données que les algorithmes en $O(n \texttt{log} n)$.

Les algorithmes quadratiques traités dans cette section sont particulièrement mauvais du point de vue de la mémoire cache. En moyenne, ils traversent la moitié des données à chaque itération. Il est donc vivement conseillé de ne pas utiliser ces algorithmes pour des tailles de données supérieures à celle du cache. Cela veut dire que si les éléments à trier occupent une dizaine de mots, il ne faut pas essayer de trier plus de quelques milliers d'éléments.