1. Tri par sélection

Principe : parcourir la liste pour trouver l'élément le plus petit (ou le plus grand), le placer en tête, puis répéter l'opération sur la portion restante jusqu'à ce que tous les éléments soient ordonnés.

function triSelection(valeurs) {
    const n = valeurs.length;
    for (let i = 0; i < n - 1; i++) {
        let indiceMin = i;
        for (let j = i + 1; j < n; j++) {
            if (valeurs[j] < valeurs[indiceMin]) {
                indiceMin = j;
            }
        }
        if (indiceMin !== i) {
            [valeurs[i], valeurs[indiceMin]] = [valeurs[indiceMin], valeurs[i]];
        }
    }
    return valeurs;
}

// Exemple d'utilisation
const donnees1 = [64, 25, 12, 22, 11];
console.log('Avant tri :', donnees1);
console.log('Après tri :', triSelection(donnees1)); // [11, 12, 22, 25, 64]

2. Tri à bulles

Principe : comparer deux éléments adjacents et les échanger s'ils sont dans le mauvais ordre, puis répéter l'opération sur toute la liste en réduisant progressivement la zone à traiter.

function triBulles(liste) {
    const taille = liste.length;
    let permutation;
    do {
        permutation = false;
        for (let i = 0; i < taille - 1; i++) {
            if (liste[i] > liste[i + 1]) {
                [liste[i], liste[i + 1]] = [liste[i + 1], liste[i]];
                permutation = true;
            }
        }
    } while (permutation);
    return liste;
}

// Exemple d'utilisation
const donnees2 = [64, 33, 24, 10, 100, 50];
console.log('Tableau initial :', donnees2);
console.log('Tableau trié :', triBulles(donnees2));

3. Tri par insertion

Principe : construire une séquence triée en prenant un élément non trié à la fois et en l'insérant à la bonne positino dans la partie déjà triée.

function triInsertion(tableau) {
    for (let i = 1; i < tableau.length; i++) {
        const elementCourant = tableau[i];
        let position = i - 1;
        while (position >= 0 && tableau[position] > elementCourant) {
            tableau[position + 1] = tableau[position];
            position--;
        }
        tableau[position + 1] = elementCourant;
    }
    return tableau;
}

// Exemple d'utilisation
const echantillon = [10, 2, 9, 3, 8, 4, 7, 5, 6];
console.log(triInsertion(echantillon)); // [2, 3, 4, 5, 6, 7, 8, 9, 10]

4. Tri fusion

Principe : diviser récursivement le tableau en moitiés jusqu'à obtenir des sous-listes d'un seul élément, puis futionner ces sous-listes de manière ordonnée.

function triFusion(liste) {
    if (liste.length <= 1) return liste;
    const milieu = Math.floor(liste.length / 2);
    const gauche = liste.slice(0, milieu);
    const droite = liste.slice(milieu);
    return fusionner(triFusion(gauche), triFusion(droite));
}

function fusionner(gauche, droite) {
    const resultat = [];
    while (gauche.length && droite.length) {
        if (gauche[0] <= droite[0]) {
            resultat.push(gauche.shift());
        } else {
            resultat.push(droite.shift());
        }
    }
    return [...resultat, ...gauche, ...droite];
}

// Exemple d'utilisation
const valeursTest = [4, 3, 2, 10, 12, 1, 5, 6];
console.log(triFusion(valeursTest)); // [1, 2, 3, 4, 5, 6, 10, 12]

5. Tri rapide (Quicksort)

Principe : choisir un élément pivot, partitionner la liste en deux sous-listes (éléments inférieurs et supérieurs au pivot), puis trier récursivement chaque sous-liste.

function triRapide(collection) {
    if (collection.length <= 1) return collection;
    const indicePivot = Math.floor(collection.length / 2);
    const pivot = collection.splice(indicePivot, 1)[0];
    const partieGauche = [];
    const partieDroite = [];
    for (const element of collection) {
        if (element < pivot) {
            partieGauche.push(element);
        } else {
            partieDroite.push(element);
        }
    }
    return [...triRapide(partieGauche), pivot, ...triRapide(partieDroite)];
}

// Exemple d'utilisation
const donneesTest = [3, 6, 8, 10, 1, 2, 1, 4, 7, 9];
console.log(triRapide(donneesTest)); // [1, 1, 2, 3, 4, 6, 7, 8, 9, 10]