IMG_0198.PNG

# Algorithmes de tri ## Complexité ### Définition La complexité d'un algorithme de tri mesure le nombre d'opérations (comparaisons,affectations,etc) nécessaires pour trier une liste de $n$ éléments. On distingue la complexité dans le meilleur des cas, le pire des cas et en moyenne. ### Notation...

# Algorithmes de tri ## Complexité ### Définition La complexité d'un algorithme de tri mesure le nombre d'opérations (comparaisons,affectations,etc) nécessaires pour trier une liste de $n$ éléments. On distingue la complexité dans le meilleur des cas, le pire des cas et en moyenne. ### Notation $\mathcal{O}$ La notation $\mathcal{O}$ (grand O) est utilisée pour exprimer la complexité d'un algorithme. Elle indique la limite supérieure du nombre d'opérations nécessaires en fonction de la taille de l'entrée ($n$). Par exemple, un algorithme de complexité $\mathcal{O}(n^2)$ signifie que le nombre d'opérations croît au plus comme le carré de la taille de l'entrée. ## Tri à bulles ### Principe Le tri à bulles consiste à parcourir la liste en comparant les éléments adjacents et en les échangeant s'ils sont mal triés. On répète ce processus jusqu'à ce qu'il n'y ait plus d'échanges à effectuer. ### Algorithme ``` Procedure tri_bulles(liste L) n ← longueur(L) répéter echange ← faux pour i de 1 à n-1 faire si L[i] > L[i+1] alors echanger(L[i], L[i+1]) echange ← vrai fin si fin pour n ← n-1 tant que echange fin procedure ``` ### Complexité - Meilleur cas: $\mathcal{O}(n)$ (liste déjà triée) - Pire cas: $\mathcal{O}(n^2)$ (liste triée en ordre inverse) - Moyenne: $\mathcal{O}(n^2)$ ## Tri par sélection ### Principe Le tri par sélection consiste à rechercher le plus petit élément de la liste et à le placer en début de liste. On répète ce processus avec le reste de la liste. ### Algorithme ``` Procedure tri_selection(liste L) n ← longueur(L) pour i de 1 à n-1 faire mini ← i pour j de i+1 à n faire si L[j] < L[mini] alors mini ← j fin si fin pour echanger(L[i], L[mini]) fin pour fin procedure ``` ### Complexité - Meilleur cas: $\mathcal{O}(n^2)$ - Pire cas: $\mathcal{O}(n^2)$ - Moyenne: $\mathcal{O}(n^2)$ ## Tri par insertion ### Principe Le tri par insertion consiste à parcourir la liste et à insérer chaque élément à sa place dans la partie déjà triée de la liste. ### Algorithme ``` Procedure tri_insertion(liste L) n ← longueur(L) pour i de 2 à n faire cle ← L[i] j ← i-1 tant que j > 0 et L[j] > cle faire L[j+1] ← L[j] j ← j-1 fin tant que L[j+1] ← cle fin pour fin procedure ``` ### Complexité - Meilleur cas: $\mathcal{O}(n)$ (liste déjà triée) - Pire cas: $\mathcal{O}(n^2)$ (liste triée en ordre inverse) - Moyenne: $\mathcal{O}(n^2)$ ## Comparaison des tris квадратиques | Algorithme | Meilleur cas | Pire cas | Moyen | | :--------------- | :------------- | :----------- | :----------- | | Tri à bulles | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | | Tri par sélection | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | | Tri par insertion | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | ## Tri rapide (Quicksort) ### Principe Le tri rapide est un algorithme de tri diviser-pour-régner. Il consiste à choisir un élément pivot, à partitionner la liste en deux sous-listes (éléments inférieurs au pivot et éléments supérieurs au pivot) et à trier récursivement les deux sous-listes. ### Algorithme ``` Procedure tri_rapide(liste L, entier gauche, entier droite) si gauche < droite alors pivot ← partitionner(L, gauche, droite) tri_rapide(L, gauche, pivot-1) tri_rapide(L, pivot+1, droite) fin si fin procedure Procedure partitionner(liste L, entier gauche, entier droite) pivot ← L[droite] i ← gauche-1 pour j de gauche à droite-1 faire si L[j]