Algorithmes de tri : concepts fondamentaux
Un algorithme de tri est utilisé pour réorganiser les éléments d'un tableau ou d'une liste donnée selon un ordre (croissant, décroissant) en utilisant l'un des opérateurs de comparaison (<, >).
Les algorithmes de tri sont fondamentaux en informatique. Ils sont utilisés comme base pour de nombreux autres algorithmes et problèmes, et leur étude permet de comprendre des concepts importants comme la complexité, la récursivité, et l'optimisation.
Terminologies des algorithmes de tri
Qu'est-ce que le tri sur place ?
Un algorithme de tri sur place utilise un espace supplémentaire constant pour produire la sortie (modifie le tableau donné uniquement). Il trie la liste uniquement en modifiant l'ordre des éléments dans la liste d'origine.
- Utilise un espace mémoire supplémentaire O(1) ou très limité
- Modifie directement le tableau d'entrée
- Exemples : tri à bulles, tri par sélection, tri par insertion, tri rapide (QuickSort), tri par tas (HeapSort)
- Contre-exemple : tri fusion (MergeSort) nécessite un tableau temporaire
// Exemple de tri sur place : tri par sélection
void triSelection(int tab[], int n) {
for (int i = 0; i < n-1; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (tab[j] < tab[min]) {
min = j;
}
}
// Échange (modifie le tableau original)
int temp = tab[i];
tab[i] = tab[min];
tab[min] = temp;
}
}- Économie de mémoire, important pour les systèmes embarqués
- Meilleure localité des données (cache)
Que sont les tri internes et externes ?
Lorsque nous exécutons un programme, nous demandons au processeur d'exécuter les instructions, de sorte que les instructions et les données utilisées doivent être placées dans la mémoire principale. Donc le tri interne et externe est basé sur cette idée.
Lorsque toutes les données sont placées en mémoire, le tri est appelé tri interne. Le processus de tri s'effectue entièrement en mémoire vive (RAM).
Exemples : Tous les algorithmes classiques (tri rapide, tri fusion, etc.)
Caractéristique : Accès rapide aux données
Lorsque toutes les données qui doivent être triées ne peuvent pas être placées en mémoire à la fois, le tri est appelé tri externe. Le tri externe est utilisé pour une énorme quantité de données.
Exemple : Merge sort externe (utilisé par les bases de données)
Caractéristique : Utilise des fichiers temporaires sur disque
Le tri externe le plus courant est une variante du tri fusion :
- Diviser le gros fichier en petits blocs qui tiennent en mémoire
- Trier chaque bloc individuellement (tri interne) et les écrire sur disque
- Fusionner les blocs triés pour obtenir le fichier final trié
Cette technique est utilisée par les systèmes de gestion de bases de données pour trier des tables contenant des millions d'enregistrements.
Stabilité des algorithmes de tri
La stabilité est principalement importante lorsque nous avons des paires clé-valeur avec des clés en double possibles (comme les noms de personnes en tant que clés et leurs détails en tant que valeurs). Et nous souhaitons trier ces objets par clés.
Un algorithme de tri est dit stable si deux objets avec des clés égales apparaissent dans le même ordre en sortie triée que dans le tableau d'entrée à trier.
Étudiants triés par nom : (Alice, 20 ans), (Bob, 22 ans), (Alice, 19 ans), (Charlie, 21 ans)
(Alice, 20 ans), (Alice, 19 ans), (Bob, 22 ans), (Charlie, 21 ans)
L'ordre des deux Alice est préservé (la première Alice reste avant la seconde)
Nous soucions-nous des tableaux simples comme un tableau d'entiers ?
Lorsque des éléments égaux sont indiscernables, comme avec des entiers, ou plus généralement, toutes les données où l'élément entier est la clé, la stabilité n'est pas un problème. La stabilité n'est pas non plus un problème si toutes les clés sont différentes.
Pouvons-nous rendre stable n'importe quel algorithme de tri ?
Tout algorithme de tri donné qui n'est pas stable peut être modifié pour être stable. Il peut y avoir des moyens spécifiques à l'algorithme de tri pour le rendre stable, mais en général, tout algorithme de tri basé sur la comparaison qui n'est pas stable par nature peut être modifié pour être stable en changeant l'opération de comparaison de clés de sorte que la comparaison de deux clés tienne compte de la position comme facteur pour des objets avec des clés égales.
| Algorithme | Stable ? | Explication |
|---|---|---|
| Tri à bulles | Oui | Échange seulement des éléments adjacents, préserve l'ordre des égaux |
| Tri par insertion | Oui | Insère les éléments en préservant l'ordre relatif |
| Tri fusion (MergeSort) | Oui | Si implémenté correctement (en cas d'égalité, prendre de la gauche d'abord) |
| Tri rapide (QuickSort) | Non | Le partitionnement peut changer l'ordre des éléments égaux |
| Tri par sélection | Non | L'échange peut déplacer un élément devant un autre égal |
| Tri par tas (HeapSort) | Non | La construction du tas ne préserve pas l'ordre |
- Tri par plusieurs clés (ex: trier par nom, puis par âge)
- Bases de données (préserver l'ordre après plusieurs tris)
- Algorithmes qui utilisent le tri comme étape intermédiaire
Comparaison des principaux algorithmes de tri
| Algorithme | Complexité (moyenne) | Complexité (pire cas) | Mémoire | Stable | Sur place |
|---|---|---|---|---|---|
| Tri à bulles | O(n²) | O(n²) | O(1) | Oui | Oui |
| Tri par insertion | O(n²) | O(n²) | O(1) | Oui | Oui |
| Tri par sélection | O(n²) | O(n²) | O(1) | Non | Oui |
| Tri rapide (QuickSort) | O(n log n) | O(n²) | O(log n) | Non | Oui |
| Tri fusion (MergeSort) | O(n log n) | O(n log n) | O(n) | Oui | Non |
| Tri par tas (HeapSort) | O(n log n) | O(n log n) | O(1) | Non | Oui |
- Tri interne : toutes les données en mémoire (la plupart des algorithmes classiques)
- Tri externe : données trop volumineuses pour tenir en mémoire (utilise des fichiers temporaires)
- Tri stable : préserve l'ordre relatif des éléments égaux
- Tri sur place : utilise peu de mémoire supplémentaire (O(1) ou O(log n))
Exemples d'application selon les besoins
Pour trier de petits tableaux (n < 50), le tri par insertion est souvent le plus efficace car il a une faible constante et est stable.
Le tri rapide (QuickSort) est généralement le plus rapide en pratique pour les grands tableaux, mais attention au pire cas.
Pour des données qui ne tiennent pas en mémoire, il faut utiliser un tri externe (généralement basé sur le tri fusion).
Si l'ordre des éléments égaux est important, il faut choisir un algorithme stable comme le tri fusion ou le tri par insertion.
- Un algorithme de tri sur place modifie directement le tableau d'entrée avec peu de mémoire supplémentaire.
- Le tri est dit interne si toutes les données tiennent en mémoire, externe sinon.
- Un tri stable préserve l'ordre relatif des éléments égaux.
- La stabilité est cruciale pour le tri par plusieurs clés et dans les bases de données.
- Le choix d'un algorithme de tri dépend de la taille des données, de la mémoire disponible, du besoin de stabilité, et des performances attendues.
- En pratique, les implémentations de
sort()dans les langages modernes utilisent souvent un hybride (ex: introsort qui combine quicksort, heapsort et insertion sort).
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.