Les algorithmes de tri sont généralement catégorisés en tri par échange, par insertion, par sélection et par fusion. Voici des implémentations JavaScript de quelques méthodes courantes.

Tri à bulles

Cet algorithme compare des éléments adjacents et les échange si nécessaire, en répétant le processus jusqu'à ce que le tableau soit ordonné.

function triBulle(liste) {
    const longueur = liste.length;
    for (let passe = 0; passe < longueur - 1; passe++) {
        for (let idx = 0; idx < longueur - passe - 1; idx++) {
            if (liste[idx] > liste[idx + 1]) {
                [liste[idx], liste[idx + 1]] = [liste[idx + 1], liste[idx]];
            }
        }
    }
    return liste;
}
console.log(triBulle([3, 6, 4, 1, 5, 8]));

Complexité temporelle : O(n²)

Tri rapide

Le tri rapide sélectionne un pivot, partitionne les éléments en sous-groupes inférieurs et supérieurs, puis applique récursivement la même méthode.

function triRapide(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[Math.floor(arr.length / 2)];
    const inférieurs = [], égaux = [], supérieurs = [];
    for (const val of arr) {
        if (val < pivot) inférieurs.push(val);
        else if (val > pivot) supérieurs.push(val);
        else égaux.push(val);
    }
    return [...triRapide(inférieurs), ...égaux, ...triRapide(supérieurs)];
}
console.log(triRapide([3, 6, 4, 1, 5, 8]));

Complexité temporelle : O(n log n) en moyenne, O(n²) dans le pire cas.

Tri par insertion

Cette méthode insère chaque élément dans une séquence déjà triée, en comparant avec les éléments précédents pour trouver sa place corercte.

function triInsertion(données) {
    const n = donnée.length;
    for (let i = 1; i < n; i++) {
        const actuel = donnée[i];
        let j = i - 1;
        while (j >= 0 && donnée[j] > actuel) {
            donnée[j + 1] = donnée[j];
            j--;
        }
        donnée[j + 1] = actuel;
    }
    return donnée;
}
console.log(triInsertion([3, 6, 9, 2, 8, 4]));

Complexité temporelle : O(n²)

Tri de Shell

Une variante du tri par insertion qui utilise des intervalles décroissants pour comparer des éléments éloignés, améliorant ainsi l'efficacité.

function triShell(tab) {
    let n = tab.length;
    let écart = Math.floor(n / 2);
    while (écart > 0) {
        for (let i = écart; i < n; i++) {
            const temp = tab[i];
            let j = i;
            while (j >= écart && tab[j - écart] > temp) {
                tab[j] = tab[j - écart];
                j -= écart;
            }
            tab[j] = temp;
        }
        écart = Math.floor(écart / 2);
    }
    return tab;
}
console.log(triShell([3, 6, 9, 2, 8, 4]));

Complexité temporelle : dépend de la séquence d'écarts, typiquement O(n log² n).

Le tri par sélection, qui extrait itérativement le minimum, et le tri par tas, utilisant une structure de tas, sont d'autrse approches courantes.