Tri par sélection en Javascript : Un algorithme simple mais efficace

Le tri par sélection est l’un des algorithmes de tri les plus simples et les plus intuitifs. Bien qu’il ne soit pas aussi efficace que certains autres algorithmes de tri pour des ensembles de données très volumineux, il reste néanmoins une méthode couramment utilisée pour trier de petites collections d’éléments. Dans cet article, nous explorerons en détail l’implémentation du tri par sélection en Javascript.

Principe de l’algorithme

L’idée fondamentale du tri par sélection est assez simple : à chaque étape, l’algorithme sélectionne l’élément minimum du tableau non trié et le place à la bonne position dans le tableau trié. Il répète ensuite ce processus pour chaque élément restant jusqu’à ce que le tableau entier soit trié.

Implémentation en Javascript

Voici une implémentation de l’algorithme de tri par sélection en Javascript :

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

Cette fonction prend un tableau arr en entrée et renvoie le tableau trié.

Exemple d’utilisation

Voici comment vous pouvez utiliser la fonction triSelection :

const tableau = [64, 34, 25, 12, 22, 11, 90];
console.log("Tableau non trié : " + tableau);
const tableauTrié = triSelection(tableau);
console.log("Tableau trié : " + tableauTrié);

Analyse de la complexité

La complexité temporelle du tri par sélection est de O(n^2) dans tous les cas, où n est le nombre d’éléments dans le tableau. Cela signifie que même pour des tableaux de petite taille, il peut ne pas être très efficace.

Voici quelques exemples de problèmes qui peuvent être résolus efficacement en utilisant l’algorithme de tri par sélection :

Trouver le plus petit élément dans un tableau non trié :

En utilisant le tri par sélection, vous pouvez facilement trouver le plus petit élément d’un tableau non trié en sélectionnant simplement le premier élément après le tri.

function trouverPlusPetitElement(arr) {
    triSelection(arr);
    return arr[0];
}

const tableau = [64, 34, 25, 12, 22, 11, 90];
console.log("Le plus petit élément du tableau est : " + trouverPlusPetitElement(tableau));

Trouver le k-ième plus petit élément dans un tableau :

Vous pouvez utiliser le tri par sélection pour trouver rapidement le k-ième plus petit élément dans un tableau en effectuant k itérations de l’algorithme de tri par sélection.

function kemePlusPetitElement(arr, k) {
    const n = arr.length;
    if (k < 1 || k > n) {
        return "Valeur de k invalide";
    }
    for (let i = 0; i < k; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr[k - 1];
}

const tableau = [64, 34, 25, 12, 22, 11, 90];
const k = 3;
console.log("Le " + k + "-ième plus petit élément du tableau est : " + kemePlusPetitElement(tableau, k));

Vérifier si un tableau est trié ou non

Vous pouvez également utiliser le tri par sélection pour vérifier si un tableau est trié ou non. Si le tableau est trié après l’application de l’algorithme de tri par sélection, alors il est trié.

function estTrié(arr) {
    const copie = [...arr];
    triSelection(copie);
    return JSON.stringify(arr) === JSON.stringify(copie);
}

const tableauTrié = [11, 22, 25, 34, 64, 90];
const tableauNonTrié = [64, 34, 25, 12, 22, 11, 90];

console.log("Le tableau trié est trié : " + estTrié(tableauTrié));
console.log("Le tableau non trié est trié : " + estTrié(tableauNonTrié));

Ces exemples illustrent différentes manières dont l’algorithme de tri par sélection peut être utilisé pour résoudre différents types de problèmes.

Cas particuliers

Optimisation pour les tableaux presque triés

Lorsque le tableau est presque trié, il est inefficace de parcourir toutes les itérations du tri par sélection. La fonction triSelectionPresqueTrié détecte si le tableau est déjà presque trié en comparant chaque élément avec son voisin. Si le tableau est presque trié, la fonction renvoie le tableau sans effectuer de tri supplémentaire.

function triSelectionPresqueTrié(arr, comparer) {
    const n = arr.length;
    let estTrié = true;
    for (let i = 0; i < n - 1; i++) {
        if (comparer) {
            if (comparer(arr[i], arr[i + 1]) > 0) {
                estTrié = false;
                break;
            }
        } else {
            if (arr[i] > arr[i + 1]) {
                estTrié = false;
                break;
            }
        }
    }
    if (estTrié) {
        return arr;
    } else {
        return triSelection(arr, comparer);
    }
}

Gestion des doublons

Lorsque le tableau contient des doublons, il est important de préserver l’ordre relatif de ces éléments. La fonction triSelectionAvecDoublons prend en charge cette situation en modifiant le processus de sélection de l’élément minimum pour inclure une condition spéciale pour préserver l’ordre relatif des doublons.

function triSelectionAvecDoublons(arr, comparer) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (comparer) {
                if (comparer(arr[j], arr[minIndex]) < 0 || (comparer(arr[j], arr[minIndex]) === 0 && j < minIndex)) {
                    minIndex = j;
                }
            } else {
                if (arr[j] < arr[minIndex] || (arr[j] === arr[minIndex] && j < minIndex)) {
                    minIndex = j;
                }
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

Traitement des valeurs spéciales

Lorsque le tableau contient des valeurs spéciales telles que NaN ou Infinity, il est nécessaire de les gérer de manière appropriée pour éviter des comportements indésirables. La fonction triSelectionAvecValeursSpéciales exclut les valeurs spéciales lors du processus de tri en les ignorant.

function triSelectionAvecValeursSpéciales(arr, comparer) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            // Vérifier si les valeurs sont spéciales
            if (Number.isNaN(arr[j]) || !Number.isFinite(arr[j])) {
                continue; // Ignorer les valeurs spéciales
            }
            if (comparer) {
                if (comparer(arr[j], arr[minIndex]) < 0) {
                    minIndex = j;
                }
            } else {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

En utilisant ces fonctions, vous pouvez adapter l’algorithme de tri par sélection pour gérer efficacement différents cas particuliers rencontrés lors de la manipulation de tableaux en JavaScript.

Exemples avancés d’utilisation de l’algorithme de tri par sélection avec des scénarios plus complexes :

1. Tri des objets par une propriété spécifique :
   Vous pouvez trier un tableau d’objets en fonction d’une propriété spécifique de chaque objet. Par exemple, supposons que vous ayez un tableau d’objets représentant des étudiants avec des propriétés telles que nom, âge et note. Vous pouvez utiliser le tri par sélection pour trier ces étudiants par leur âge ou leur note.

// Exemple de tri d'étudiants par âge
const etudiants = [
    { nom: "Alice", age: 22 },
    { nom: "Bob", age: 20 },
    { nom: "Charlie", age: 25 }
];

triSelection(etudiants, (a, b) => a.age - b.age);

console.log("Étudiants triés par âge :");
console.log(etudiants);

2. Tri selon plusieurs critères :
   Vous pouvez trier un tableau selon plusieurs critères. Par exemple, trier d’abord par un critère, puis par un autre en cas d’égalité. Cela peut être utile pour trier des éléments de manière plus sophistiquée.

// Exemple de tri de produits par prix, puis par nom en cas d'égalité de prix
const produits = [
    { nom: "Livre", prix: 15 },
    { nom: "Stylo", prix: 5 },
    { nom: "Cahier", prix: 10 },
    { nom: "Stylo Rouge", prix: 5 }
];

triSelection(produits, (a, b) => {
    if (a.prix === b.prix) {
        return a.nom.localeCompare(b.nom);
    }
    return a.prix - b.prix;
});

console.log("Produits triés par prix, puis par nom :");
console.log(produits);

3. Tri selon une logique complexe :
   Vous pouvez utiliser une fonction de comparaison personnalisée pour implémenter une logique de tri complexe. Par exemple, trier des chaînes de caractères en fonction de leur longueur ou trier des dates dans un ordre spécifique.

// Exemple de tri de chaînes de caractères par longueur décroissante
const mots = ["abricot", "pomme", "orange", "banane", "kiwi"];

triSelection(mots, (a, b) => b.length - a.length);

console.log("Mots triés par longueur décroissante :");
console.log(mots);

Ces exemples illustrent comment l’algorithme de tri par sélection peut être utilisé de manière avancée pour trier des données selon différents critères et logiques, offrant ainsi une flexibilité et une puissance supplémentaires dans le traitement des tableaux de données complexes.

Erreurs courantes à éviter lors de l’implémentation de l’algorithme de tri par sélection, et des astuces pour les éviter

1. Oublier de vérifier les entrées invalides :
   Assurez-vous de vérifier les entrées invalides, telles que les tableaux vides ou les tableaux contenant un seul élément, et traitez-les de manière appropriée pour éviter des erreurs inattendues.

function triSelection(arr, comparer) {
    if (!Array.isArray(arr) || arr.length <= 1) {
        return arr; // Retourne le tableau inchangé pour les entrées invalides
    }
    // Implémentation de l'algorithme de tri par sélection
}

2. Omettre la gestion des types de données non standard :
   Assurez-vous de prendre en compte les types de données non standard ou complexes en fournissant une fonction de comparaison personnalisée qui peut gérer ces cas spécifiques.

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

// Utilisation avec une fonction de comparaison personnalisée
const tableau = [ { id: 3, name: "John" }, { id: 1, name: "Alice" }, { id: 2, name: "Bob" } ];
const comparer = (a, b) => a.id - b.id; // Comparaison basée sur les identifiants
triSelection(tableau, comparer);

3. Ne pas optimiser pour les tableaux presque triés :
   Si le tableau est déjà presque trié, évitez de parcourir toutes les itérations de l’algorithme de tri par sélection en vérifiant d’abord si le tableau est presque trié.

function triSelectionPresqueTrié(arr, comparer) {
    const n = arr.length;
    let estTrié = true;
    for (let i = 0; i < n - 1; i++) {
        if (comparer(arr[i], arr[i + 1]) > 0) {
            estTrié = false;
            break;
        }
    }
    if (estTrié) {
        return arr;
    } else {
        return triSelection(arr, comparer);
    }
}

4. Oublier de prendre en compte les doublons :
   Si votre tableau peut contenir des doublons et que vous souhaitez préserver l’ordre relatif de ces éléments, assurez-vous d’ajuster l’algorithme de tri en conséquence.

function triSelectionAvecDoublons(arr, comparer) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (comparer(arr[j], arr[minIndex]) < 0 || (comparer(arr[j], arr[minIndex]) === 0 && j < minIndex)) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

En évitant ces erreurs courantes et en appliquant ces astuces, vous pouvez améliorer la robustesse et l’efficacité de votre implémentation de l’algorithme de tri par sélection.

Conclusion

Le tri par sélection est un algorithme simple à comprendre et à implémenter. Bien qu’il ne soit pas aussi rapide que certains autres algorithmes de tri pour de grandes quantités de données, il peut être utile pour trier de petites collections d’éléments. En comprenant le fonctionnement de cet algorithme, vous aurez une base solide pour comprendre d’autres algorithmes de tri plus complexes.