Bonsoir,
1)
Il s'agit d'un complexité linéaire (on dit complexité en O(n) aussi, avec n la taille de la liste à trier).
2)
Il s'agit d'une complexité quadratique (on dit aussi complexité en O(n²)).
C'est la complexité dans le pire des cas pour le tri par insertion ou sélection.
3)
Je te conseille fortement, de regarder des vidéos explicatives pour ces algorithmes de tri, à l'écrit ça risque d'être incompréhensible.
Tri fusion ("Merge Sort"): Notion de "Diviser pour mieux régner"; l'algorithme utilise la récursivité (fonction qui s'appelle elle-même). A chaque appel de la fonction on coupe la liste (puis les sous-liste) en deux et on trie chacun des groupes indépendamment. Puis on fusionne les groupes qui sont déjà triés. Sa complexité est en O(nlog(n)) (complexité sous-quadratique) dans le pire des cas et en O(nlog(n) / 2) (complexité sous-quadratique) dans le meilleur des cas. Les mathématiciens ont montré qu'on ne peut pas faire un algorithme de tri avec une meilleure complexité que la complexité sous-quadratique. Le tri fusion fait donc partie des algorithmes de tri les plus performants.
Tri rapide ("Quicksort"): Notion de "Diviser pour mieux régner"; l'algorithme utilise la récursivité. A chaque appel de la fonction, on choisir un pivot, puis on effectue une partition des éléments à trier (une sous-liste). Un premier groupe est constitué de valeurs inférieures au pivot et un deuxième avec les valeurs supérieures. On répète l'opération sur les sous-listes (divisions successives) puis on obtient la liste trier. Sa complexité est en O(n²/2) dans le pire des cas et en O(nlog(n)) (complexité sous-quadratique) dans le meilleur des cas.
Tri à bulles: Regarde une vidéo, ça va être beaucoup plus simple, c'est une sorte de mélange du tri par sélection et insertion. Complexité quadratique O(n²).
Source: Mon cours de prépa 2ème année (PT*). Tu pourras mettre les sources des vidéos que tu auras regardé.
Bonne soirée.
