Chapitre 15. Les algorithmes de tri

Les tris ont une très grande utilité dans la programmation et dans le traitement de données. On peut les utiliser par exemple dans :
Le classement des données
La recherche d’information
Les algorithmes de tri ont chacun une efficacité (que l’on évaluera par sa complexité) et aussi (ou parfois) une contrainte d’utilisation, ou un domaine d’utilisation dans lequel un tri est plus adapté qu’un autre.
Les tris sont parfois si souvent utilisés que l’on n’y prête plus attention. Il est donc intéressant de savoir repérer les situations dans lesquelles il faudra les implémenter et utiliser le plus adapté.
On distingue :
C’est un tri qui se fait en mémoire secondaire, c’est-à-dire sur les disques de stock-age de masse. La limite de l’espace de travail est donc égale à la moitié de l’espace de stockage disponible.C’est un tri qui se fait en mémoire centrale. Il y a donc une quantité de mémoire finie et limitée pour effectuer le travail de tri. Cette taille mémoire de travail ne peut pas être prise égale à la taille de la RAM divisée par 2 car sur une machine qui possède 8 Go de RAM, une partie est déjà occupée par le système d’exploitation (1 Go sont par exemple occupés par Windows) et les machines virtuelles qui permettent de faire fonctionner les programmes (Java, C++…) ont une limite par défaut (1 Go pour Java, 1/4 de la taille mémoire de la machine physique). Python n’a pas de limite de taille comme dans les langages compilés. Il utilise tout l’environnement disponible…