min_index =j
finir si
fin pour
// Échange l'élément minimum trouvé avec le premier élément
échanger la liste[i] et la liste[min_index]
fin pour
fin de la procédure
```
* Efficacité :
* Meilleur cas : O(n
2
)
* Cas moyen : O(n
2
)
* Dans le pire des cas : O(n
2
)
* Complexité spatiale : O(1) (tri sur place)
* Mise en œuvre : Relativement simple.
* Cas d'utilisation : Fonctionne légèrement mieux que Bubble Sort dans certains cas, mais ne convient toujours pas aux grands ensembles de données. Le nombre de swaps est limité à O(n), ce qui peut être utile si les écritures mémoire sont coûteuses.
3. Tri par insertion
* Concept : Construit la liste triée un élément à la fois. Il parcourt les données d'entrée, supprime un élément à la fois, trouve la position correcte dans la liste triée et l'insère là.
* Pseudocode :
```
procédure insertionSort(liste :tableau d'éléments)
n =longueur (liste)
pour i =1 à n-1 faire
clé =liste[i]
j =je - 1
// Déplace les éléments de list[0..i-1], qui sont supérieurs à key,
// à une position en avance sur leur position actuelle
tandis que j>=0 et list[j]> key do
liste[j+1] =liste[j]
j =j - 1
terminer pendant que
liste[j+1] =clé
fin pour
fin de la procédure
```
* Efficacité :
* Meilleur cas : O(n) (Lorsque la liste est déjà triée)
* Cas moyen : O(n
2
)
* Dans le pire des cas : O(n
2
)
* Complexité spatiale : O(1) (tri sur place)
* Mise en œuvre : Simple et efficace pour les petits ensembles de données ou les données presque triées.
* Cas d'utilisation : Idéal pour les petites listes ou lorsque vous vous attendez à ce que les données d'entrée soient principalement triées. De plus, il s'agit d'un algorithme *en ligne*, ce qui signifie qu'il peut trier une liste au fur et à mesure qu'il la reçoit.
4. Fusionner le tri
* Concept : Un algorithme diviser pour régner. Il divise la liste en sous-listes plus petites, trie les sous-listes de manière récursive, puis les fusionne.
* Pseudocode :
```
procédure mergeSort(liste :tableau d'éléments)
n =longueur (liste)
si n <=1 alors
liste de retour // Déjà trié
finir si
// Divise la liste en deux moitiés
milieu =n/2
leftList =liste[0 à mi-1]
rightList =liste[milieu à n-1]
// Trie récursivement chaque moitié
listegauche =mergeSort(listegauche)
rightList =mergeSort (rightList)
// Fusionner les moitiés triées
retourner la fusion (leftList, rightList)
fin de la procédure
procédure de fusion (leftList :tableau d'éléments, rightList :tableau d'éléments)
resultList =nouveau tableau
tandis que leftList n'est pas vide et rightList n'est pas vide, faites
si leftList[0] <=rightList[0] alors
ajouter leftList[0] à resultList
supprimer leftList[0] de leftList
autre
ajouter rightList[0] à resultList
supprimer rightList[0] de rightList
finir si
terminer pendant que
// Ajoute tous les éléments restants de leftList ou rightList
ajouter tous les éléments restants de leftList à resultList
ajouter tous les éléments restants de rightList à resultList
retourner la liste des résultats
fin de la procédure
```
* Efficacité :
* Meilleur cas : O (n journal n)
* Cas moyen : O (n journal n)
* Dans le pire des cas : O (n journal n)
* Complexité spatiale : O(n) (Nécessite un espace supplémentaire pour la fusion)
* Mise en œuvre : Plus complexe que les algorithmes précédents, mais offre de bonnes performances pour les grands ensembles de données.
* Cas d'utilisation : Convient au tri de grandes listes où des performances constantes sont importantes.
5. Tri rapide
* Concept : Également un algorithme diviser pour régner. Il sélectionne un élément comme pivot et partitionne le tableau donné autour du pivot choisi.
* Pseudocode :
```
procédure quickSort(list :tableau d'éléments, low :int, high :int)
si faible <élevé alors
// Index de partitionnement, arr[p] est maintenant au bon endroit
p =partition (liste, basse, haute)
// Trier séparément les éléments avant la partition et après la partition
tri rapide (liste, bas, p-1)
tri rapide (liste, p+1, élevé)
finir si
fin de la procédure
partition de procédure (liste :tableau d'éléments, low :int, high :int)
pivot =list[high] // Choisissez le dernier élément comme pivot
i =faible - 1 // Indice du plus petit élément
pour j =faible à élevé-1 do
// Si l'élément courant est inférieur ou égal au pivot
si liste[j] <=pivot alors
i =i + 1 // incrémente l'index du plus petit élément
échanger la liste[i] et la liste[j]
finir si
fin pour
swap list[i + 1] et list[high]
retourner i + 1
fin de la procédure
```
* Efficacité :
* Meilleur cas : O(n log n) (Lorsque le pivot est toujours la médiane)
* Cas moyen : O (n journal n)
* Dans le pire des cas : O(n
2
) (Lorsque le pivot est toujours l'élément le plus petit ou le plus grand)
* Complexité spatiale : O(log n) (En raison d'appels récursifs, peut être O(n) dans le pire des cas)
* Mise en œuvre : Généralement rapide en pratique, mais ses performances dans le pire des cas peuvent être préoccupantes. Le choix du pivot affecte considérablement ses performances.
* Cas d'utilisation : Souvent l’algorithme de tri le plus rapide en pratique pour les grands ensembles de données. Cependant, ses performances dans le pire des cas doivent être prises en compte. De nombreuses implémentations utilisent la randomisation ou d'autres techniques pour éviter le pire des cas.
6. Tri par tas
* Concept : Construit un tas maximum (ou tas min) à partir des données d'entrée, puis extrait à plusieurs reprises l'élément racine (l'élément le plus grand ou le plus petit) et le place à la fin du tableau trié.
* Pseudocode :
```
procédure tasSort(liste :tableau d'éléments)
n =longueur (liste)
// Construire le tas maximum
pour i =n/2 - 1 jusqu'à 0 faire
heapify(liste, n, i)
fin pour
// Extrait un par un un élément du tas
pour i =n-1 jusqu'à 0 faire
swap list[0] et list[i] // Déplace la racine actuelle vers la fin
// appelle max heapify sur le tas réduit
heapify(liste, je, 0)
fin pour
fin de la procédure
procédure heapify(list :tableau d'éléments, n :int, i :int)
plus grand =i // Initialise le plus grand en tant que racine
gauche =2*i + 1
droite =2*i + 2
// Si l'enfant de gauche est plus grand que la racine
si gauche liste [la plus grande] alors
le plus grand =gauche
finir si
// Si l'enfant de droite est plus grand que le plus grand jusqu'à présent
si droite liste [la plus grande] alors
le plus grand =à droite
finir si
// Si le plus grand n'est pas la racine
si le plus grand !=i alors
échanger la liste[i] et la liste[la plus grande]
// Heapify récursivement le sous-arbre affecté
tas (liste, n, le plus grand)
finir si
fin de la procédure
```
* Efficacité :
* Meilleur cas : O (n journal n)
* Cas moyen : O (n journal n)
* Dans le pire des cas : O (n journal n)
* Complexité spatiale : O(1) (tri sur place)
* Mise en œuvre : Plus complexe que des algorithmes plus simples, mais garantit des performances O(n log n).
* Cas d'utilisation : Un bon choix lorsque vous avez besoin de performances O(n log n) garanties et d'un tri sur place est souhaitable. Utilisé dans les implémentations de files d'attente prioritaires.
Tableau récapitulatif des efficacités
| Algorithme | Meilleur cas | Cas moyen | Pire des cas | Complexité spatiale |
|---------|-----------|--------------|------------|-------------------|
| Tri à bulles | O(n) | O(n
2
) | O(n
2
) | O(1) |
| Sélection Trier | O(n
2
) | O(n
2
) | O(n
2
) | O(1) |
| Tri par insertion | O(n) | O(n
2
) | O(n
2
) | O(1) |
| Fusionner le tri | O(n journal n) | O(n journal n) | O(n journal n) | O(n) |
| Tri rapide | O(n journal n) | O(n journal n) | O(n
2
) | O(logn) |
| Tri en tas | O(n journal n) | O(n journal n) | O(n journal n) | O(1) |
Différences clés en termes d'efficacité et de mise en œuvre :
* Quadratique ou logarithmique : Algorithmes avec O(n
2
) (Bulle, Sélection, Insertion) ne conviennent qu'aux petits ensembles de données. Les algorithmes avec une efficacité O(n log n) (Fusion, Quick, Heap) sont beaucoup plus efficaces pour les ensembles de données plus volumineux.
* Diviser pour régner : Le tri par fusion et le tri rapide utilisent la stratégie diviser pour régner, qui permet un tri plus efficace des grands ensembles de données.
* Tri sur place : Le tri à bulles, le tri par sélection, le tri par insertion et le tri par tas sont des algorithmes de tri sur place, ce qui signifie qu'ils ne nécessitent pas de mémoire supplémentaire importante. Le tri par fusion nécessite O(n) d'espace supplémentaire pour la fusion. Le tri rapide nécessite O(log n) en moyenne mais un espace O(n) dans le pire des cas en raison des appels récursifs.
* Stabilité : Un algorithme de tri est *stable* si les éléments de valeurs égales conservent leur ordre relatif après le tri. Le tri par fusion et le tri par insertion sont stables, tandis que le tri par tas et le tri rapide (sous leur forme de base) ne le sont pas. La stabilité peut être importante dans certaines applications.
* Choix pivot (tri rapide) : Les performances de Quick Sort dépendent fortement du choix de l’élément pivot. De mauvais choix de pivot peuvent conduire au pire des cas O(n
2
) performance.
* Complexité de mise en œuvre : Le tri à bulles et le tri par insertion sont les plus simples à mettre en œuvre. Le tri par fusion, le tri rapide et le tri par tas sont plus complexes.
* Adaptabilité : Le tri par insertion est adaptatif, ce qui signifie que ses performances s'améliorent si les données d'entrée sont déjà partiellement triées.
Choisir le bon algorithme :
Le meilleur algorithme de tri à utiliser dépend de l'application spécifique et des caractéristiques des données. Tenez compte de ces facteurs :
* Taille de l'ensemble de données : Pour les très petits ensembles de données, la simplicité du tri à bulles ou du tri par insertion peut être suffisante. Pour les ensembles de données plus volumineux, le tri par fusion, le tri rapide ou le tri par tas sont généralement de meilleurs choix.
* Niveau de tri : Si les données sont déjà en grande partie triées, le tri par insertion peut être l'option la plus rapide.
* Contraintes de mémoire : Si la mémoire est limitée, les algorithmes de tri sur place tels que le tri à bulles, le tri par sélection, le tri par insertion et le tri par tas sont préférés.
* Exigences de stabilité : Si la stabilité est requise, choisissez un algorithme de tri stable comme le tri par fusion ou le tri par insertion.
* Performances dans le pire des cas : Si vous avez besoin de performances garanties, évitez le tri rapide (à moins qu'il ne soit mis en œuvre avec une randomisation pivot ou d'autres stratégies pour atténuer le pire des cas).
* Facilité de mise en œuvre et de maintenance : Considérez le compromis entre performances et complexité de mise en œuvre.
J'espère que cette explication détaillée vous aidera ! Faites-moi savoir si vous avez d'autres questions.
