Fondamentaux des Algorithmes de Tri
Classification des Algorithmes
Les algorithmes de tri se divisent en deux catégories principales :
- Tri par comparaison : Détermine l'ordre relatif des éléments en les comparant. La complexité temporelle ne peut pas être inférieure à O(n log n), on parle donc de tri linéaire non comparatif dans le cas inverse.
- Tri sans comparaison : Ne repose pas sur la comparaison directe des éléments. Il peut atteindre une complexité linéaire O(n), franchissant ainsi la limite inférieure des tris par comparaison.
Concepts Clés
- Stabilité : Un algorithme est stable si deux éléments de même valeur conservent leur ordre relatif initial après le tri.
- Complexité temporelle : Mesure le nombre total d'opérations effectuées, indiquant comment le temps d'exécution évolue en fonction de la taille des données (n).
- Complexité spatiale : Quantifie la mémoire supplémentaire nécessaire à l'exécution de l'algorithme en fonction de la taille des données.
- Tri à Bulles (Bubble Sort)
Le tri à bulles est un algorithme simple qui parcourt répétitivement la liste, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Les éléments les plus petits "remontent" progressivement vers le début du tableau.
Implémentation
const triABulles = (tableau) => {
const n = tableau.length;
for (let i = 0; i < n - 1; i++) {
let echangeEffectue = false;
for (let j = 0; j < n - 1 - i; j++) {
if (tableau[j] > tableau[j + 1]) {
[tableau[j], tableau[j + 1]] = [tableau[j + 1], tableau[j]];
echangeEffectue = true;
}
}
if (!echangeEffectue) break;
}
return tableau;
};
- Tri par Sélection (Selection Sort)
Ce divise le tableau en deux zones : une zone triée et une zone non triée. À chaque itération, l'élément le plus petit de la zone non triée est sélectionné et déplacé à la fin de la zone triée.
Implémentation
const triParSelection = (data) => {
const taille = data.length;
for (let i = 0; i < taille - 1; i++) {
let indexMin = i;
for (let j = i + 1; j < taille; j++) {
if (data[j] < data[indexMin]) {
indexMin = j;
}
}
if (indexMin !== i) {
[data[i], data[indexMin]] = [data[indexMin], data[i]];
}
}
return data;
};
Le tri par sélection est stable en termes de complexité temporelle O(n²) dans tous les cas. Son avantage principal réside dans sa complexité spatiale O(1).
- Tri par Insertion (Insertion Sort)
Cet algorithme consrtuit le tableau trié un élément à la fois. Il insère chaque nouvel élément à sa position correcte dans la partie déjà triée du tableau.
Implémentation
const triParInsertion = (items) => {
for (let i = 1; i < items.length; i++) {
let valeurCourante = items[i];
let trou = i - 1;
while (trou >= 0 && items[trou] > valeurCourante) {
items[trou + 1] = items[trou];
trou--;
}
items[trou + 1] = valeurCourante;
}
return items;
};
Le tri par insertion est généralement implémenté en place (O(1) en espace). Il est très efficace pour les tableaux de petite taille ou presque triés.
- Tri de Shell (Shell Sort)
Inventé en 1959, c'est une généralisation du tri par insertion qui permet d'échanger des éléments éloignés. Il utilise une séquence de gaps (écarts) décroissante pour trier les sous-séquences.
Implémentation
const triDeShell = (sequence) => {
const n = sequence.length;
for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < n; i++) {
let temp = sequence[i];
let j = i;
while (j >= gap && sequence[j - gap] > temp) {
sequence[j] = sequence[j - gap];
j -= gap;
}
sequence[j] = temp;
}
}
return sequence;
};
L'efficacité du tri de Shell dépend fortement de la séquence de gaps utilisée. Il brise la limite O(n²) des tris par insertion simples.
- Tri Fusion (Merge Sort)
Basé sur le principe diviser pour régner, le tri fusion divise le tableau en deux moitiés, trie chaque moitié récursivement, puis fusionne les deux moitiés triées.
Implémentation
const triFusion = (array) => {
if (array.length <= 1) return array;
const milieu = Math.floor(array.length / 2);
const gauche = triFusion(array.slice(0, milieu));
const droite = triFusion(array.slice(milieu));
return fusionner(gauche, droite);
};
const fusionner = (gauche, droite) => {
let resultat = [];
let g = 0, d = 0;
while (g < gauche.length && d < droite.length) {
if (gauche[g] <= droite[d]) {
resultat.push(gauche[g++]);
} else {
resultat.push(droite[d++]);
}
}
return resultat.concat(gauche.slice(g)).concat(droite.slice(d));
};
Le tri fusion est stable et garantit une complexité temporelle O(n log n) dans tous les cas, au prix d'une complexité spatiale O(n).
- Tri Rapide (Quick Sort)
Le tri rapide utilise également le diviser pour régner. Il sélectionne un élément "pivot", partitionne le tableau de sorte que les éléments inférieurs soient à gauche et les supérieurs à droite, puis trie récursivement les sous-tableaux.
Implémentation
const triRapide = (arr, low = 0, high = arr.length - 1) => {
if (low < high) {
const indexPivot = partitionner(arr, low, high);
triRapide(arr, low, indexPivot - 1);
triRapide(arr, indexPivot + 1, high);
}
return arr;
};
const partitionner = (arr, low, high) => {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
};
- Tri par Tas (Heap Sort)
Ce tri utilise une structure de données de type tas (heap), spécifiquement un tas max. Il construit d'abord le tas, puis extrait répétitivement l'élément maximum pour le placer à la fin du tableau.
Implémentation
const triParTas = (data) => {
const n = data.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
tamiser(data, n, i);
}
for (let i = n - 1; i > 0; i--) {
[data[0], data[i]] = [data[i], data[0]];
tamiser(data, i, 0);
}
return data;
};
const tamiser = (data, tailleTas, indexRacine) => {
let plusGrand = indexRacine;
const gauche = 2 * indexRacine + 1;
const droite = 2 * indexRacine + 2;
if (gauche < tailleTas && data[gauche] > data[plusGrand]) plusGrand = gauche;
if (droite < tailleTas && data[droite] > data[plusGrand]) plusGrand = droite;
if (plusGrand !== indexRacine) {
[data[indexRacine], data[plusGrand]] = [data[plusGrand], data[indexRacine]];
tamiser(data, tailleTas, plusGrand);
}
};
- Tri par Dénombremant (Counting Sort)
Algorithme non comparatif qui compte le nombre d'occurrences de chaque valeur unique pour déterminer leur position finale. Il nécessite que les données soient des entiers dans une plage connue.
Implémentation
const triParDenombrement = (input, maxVal) => {
const occurrences = new Array(maxVal + 1).fill(0);
const sortie = new Array(input.length);
for (const num of input) {
occurrences[num]++;
}
for (let i = 1; i <= maxVal; i++) {
occurrences[i] += occurrences[i - 1];
}
for (let i = input.length - 1; i >= 0; i--) {
const val = input[i];
sortie[occurrences[val] - 1] = val;
occurrences[val]--;
}
return sortie;
};
Avec une complexité de O(n+k), il est extrêmement rapide lorsque l'écart entre la valeur maximale et minimale (k) est petit.
- Tri par Compartiments (Bucket Sort)
Extension du tri par dénombrement, il distribue les éléments dans un nombre fini de compartiments (buckets). Chaque compartiment est ensuite trié individuellement, souvent avec un autre algorithme comme le tri par insertion.
Implémentation
const triParCompartiments = (elements, tailleCompartiment = 5) => {
if (elements.length === 0) return elements;
let minVal = elements[0], maxVal = elements[0];
for (const el of elements) {
if (el < minVal) minVal = el;
if (el > maxVal) maxVal = el;
}
const nbCompartiments = Math.floor((maxVal - minVal) / tailleCompartiment) + 1;
const compartiments = Array.from({ length: nbCompartiments }, () => []);
for (const el of elements) {
const idx = Math.floor((el - minVal) / tailleCompartiment);
compartiments[idx].push(el);
}
const resultat = [];
for (const compartiment of compartiments) {
if (compartiment.length > 0) {
triParInsertion(compartiment);
resultat.push(...compartiment);
}
}
return resultat;
};
Le tri par compartiments atteint O(n) dans le meilleur cas, mais sa performance dépend de la distribution uniforme des données et de la taille des compartiments.
- Tri par Base (Radix Sort)
Ce tri non comparatif trie les entiers en les regroupant par chiffres individuels (ou "radix"). Il commence par le chiffre de poids le plus faible (unités) et progresse vers le chiffre de poids le plus fort, en utilisant un tri stable (comme le tri par compartiments) à chaque étape.
Implémentasion
const triParBase = (tableau, nombreMaxDigits) => {
let mod = 10;
let diviseur = 1;
for (let digit = 0; digit < nombreMaxDigits; digit++) {
const buckets = Array.from({ length: 10 }, () => []);
for (const num of tableau) {
const bucketIdx = Math.floor((num % mod) / diviseur);
buckets[bucketIdx].push(num);
}
let pos = 0;
for (const bucket of buckets) {
for (const val of bucket) {
tableau[pos++] = val;
}
}
mod *= 10;
diviseur *= 10;
}
return tableau;
};
Le tri par base est stable avec une complexité temporelle de O(d * (n + k)), où d est le nombre de chiffres. Il est très efficace pour trier de grandes listes d'entiers de longueur fixe.