Un algorithme de tri permet d'organiser une collection d'objets selon un ordre déterminé (croissant , alphabétique ...). Supposons qu'on a un paquet de 10 cartes . Le but est de les trier le plus rapidement possible . Une méthode intuitive est de parcourir toutes les cartes pour trouver celle qui a la plus faible valeur . Ensuite on l'extrait et on la range . On refait le processus jusqu’à ce que toutes les cartes soient ranges dans l'ordre .
Ainsi, le nombre de cartes parcouru est de 10+9+8+...+1 = 50. C’est le tri par insertion
Il est possible de déterminer comment évolue le nombre de parcours d'éléments en fonction de la taille des données à trier . C'est la complexité d’un algorithme . C'est un critère majeur pour comparer les performances de algorithmes de tri .
Le tri par insertion est intuitive mais il est fastidieux. En effet , pour N cartes a trier , le nombre de parcours nécessaire augmente au carré : il est donc de complexité de N² . Pour 10 cartes , on a 50 parcours . Pour 100 cartes on en a 5000.
Il existe un algorithme plus performant qui est le tri rapide dont la complexité est meilleur. Il est de N*log(N) . Ainsi pour trier 100 cartes, on a besoin de 650 parcours au lieu de 5000 avec le tri rapide .
En savoir plus
Infotéo. (2016, 28 octobre). Algorithme de trie [Vidéo]. Youtube. https://www.youtube.com/watch?v=ra79TDfotno
ScienceEtonnante. (2020, 17 juillet). Nos algorithmes pourraient-ils être beaucoup plus rapides ? (P=NP ?). [Vidéo]. Youtube. https://www.youtube.com/watch?v=AgtOCNCejQ8
AlgoRythmics. (2011, 29 mars). Bubble-sort with Hungarian ("Csángó") folk dance. [Vidéo]. Youtube. https://www.youtube.com/watch?v=lyZQPjUT5B4
Timo Bingmann. (2013, 20 mai). 15 Sorting Algorithms in 6 Minutes. [Vidéo]. Youtube. https://www.youtube.com/watch?v=kPRA0W1kECg
Article paru dans Je Science donc J'écris n°24 - Janvier 2021
