Tri par insertion en JavaScript : Un algorithme simple mais efficace
Le tri par insertion est l’un des algorithmes de tri les plus simples et les plus intuitifs. Bien qu’il ne soit pas aussi rapide que certains des algorithmes de tri plus avancés comme le tri rapide ou le tri fusion, il est souvent utilisé dans les cas où le nombre d’éléments à trier est relativement petit ou lorsque la performance n’est pas critique.
Comprendre le principe
L’idée derrière le tri par insertion est assez simple : vous parcourez un tableau, en prenant chaque élément un par un, et vous l’insérez à sa place correcte parmi les éléments déjà triés. En d’autres termes, vous construisez progressivement une partie triée du tableau, en insérant chaque nouvel élément dans la position appropriée.
Implémentation en JavaScript
Voici une implémentation de l’algorithme de tri par insertion en JavaScript :
function triInsertion(tab) {
for (let i = 1; i < tab.length; i++) {
let valeurCourante = tab[i];
let j = i - 1;
// Déplacer les éléments du tableau trié qui sont plus grands que la valeur courante
// vers la droite d'une position
while (j >= 0 && tab[j] > valeurCourante) {
tab[j + 1] = tab[j];
j--;
}
// Insérer la valeur courante à sa position correcte dans le tableau trié
tab[j + 1] = valeurCourante;
}
return tab;
}
// Exemple d'utilisation
let tableau = [5, 2, 4, 6, 1, 3];
console.log("Avant le tri :", tableau);
triInsertion(tableau);
console.log("Après le tri :", tableau);Analyse de la complexité
La complexité temporelle du tri par insertion dépend de la disposition initiale des éléments dans le tableau. Dans le pire des cas, lorsque le tableau est initialement trié dans l’ordre inverse, le tri par insertion nécessite O(n^2) comparaisons et O(n^2) échanges, où n est le nombre d’éléments à trier. Dans le meilleur des cas, lorsque le tableau est déjà trié, le tri par insertion nécessite seulement O(n) comparaisons et O(1) échanges.
Avantages et inconvénients
Avantages :
- Simplicité : L’algorithme est facile à comprendre et à mettre en œuvre.
- Adaptabilité : Le tri par insertion peut être efficace pour trier de petites quantités de données ou lorsque le tableau est déjà presque trié.
Inconvénients :
- Performance : Pour de grandes quantités de données, le tri par insertion peut être beaucoup moins efficace que des algorithmes plus avancés.
- Complexité temporelle : Dans le pire des cas, la complexité temporelle quadratique peut rendre l’algorithme inefficace.
Voici comment vous pourriez mettre en œuvre ces exemples avec du code JavaScript utilisant le tri par insertion :
Gestion des contacts :
function trierContacts(contacts) {
return triInsertion(contacts);
}
// Exemple d'utilisation
let contacts = ["Alice", "Bob", "Eve", "David"];
console.log("Contacts avant le tri :", contacts);
contacts = trierContacts(contacts);
console.log("Contacts après le tri :", contacts);Listes de tâches
function trierTaches(taches) {
return triInsertion(taches);
}
// Exemple d'utilisation
let taches = [
{ nom: "Faire les courses", priorite: 2 },
{ nom: "Payer les factures", priorite: 1 },
{ nom: "Répondre aux e-mails", priorite: 3 }
];
console.log("Tâches avant le tri :", taches);
taches = trierTaches(taches);
console.log("Tâches après le tri :", taches);Historique des transactions
function trierTransactions(transactions) {
return triInsertion(transactions);
}
// Exemple d'utilisation
let transactions = [
{ montant: 100, date: "2024-02-15" },
{ montant: 50, date: "2024-02-10" },
{ montant: 200, date: "2024-02-20" }
];
console.log("Transactions avant le tri :", transactions);
transactions = trierTransactions(transactions);
console.log("Transactions après le tri :", transactions);Et ainsi de suite, vous pouvez adapter ces exemples à d’autres applications en utilisant le tri par insertion pour trier les données selon les besoins spécifiques de votre application.
Voici une réécriture avec des sous-titres et des exemples de code pour chaque cas particulier :
1. Tableau déjà trié.;
Si le tableau est déjà trié, le tri par insertion offre des performances optimales. Il nécessite un nombre minimal de comparaisons et d’échanges.
let tableauTrié = [1, 2, 3, 4, 5];
triInsertion(tableauTrié);
console.log("Tableau trié :", tableauTrié);2. Tableau inversé
En revanche, si le tableau est trié dans l’ordre inverse, le tri par insertion nécessitera le maximum de déplacements.
let tableauInverse = [5, 4, 3, 2, 1];
triInsertion(tableauInverse);
console.log("Tableau trié inversé :", tableauInverse);3. Éléments égaux
Si le tableau contient des éléments égaux, le tri par insertion maintiendra leur ordre relatif.
let tableauEgaux = [3, 2, 5, 2, 4];
triInsertion(tableauEgaux);
console.log("Tableau trié avec éléments égaux :", tableauEgaux);4. Optimisation de la copie
Une optimisation courante consiste à utiliser un seul déplacement pour faire de la place pour l’élément à insérer, puis à placer cet élément à sa position correcte.
function triInsertionOptimise(tab) {
for (let i = 1; i < tab.length; i++) {
let valeurCourante = tab[i];
let j = i - 1;
// Trouver l'emplacement pour l'insertion
while (j >= 0 && tab[j] > valeurCourante) {
tab[j + 1] = tab[j];
j--;
}
// Insérer la valeur courante
tab[j + 1] = valeurCourante;
}
return tab;
}5. Taille du tableau
Le tri par insertion est plus efficace pour trier de petits tableaux en raison de sa complexité quadratique.
let grandTableau = [/* beaucoup d'éléments */];
triInsertionOptimise(grandTableau);
console.log("Grand tableau trié :", grandTableau);En prenant en compte ces différents cas particuliers lors de l’implémentation et de l’utilisation du tri par insertion en JavaScript, vous pouvez adapter votre approche en fonction des besoins spécifiques de votre application pour garantir des performances optimales.
Voici quelques exemples avancés illustrant l’utilisation du tri par insertion en JavaScript dans des scénarios plus complexes :
1. Tri d’objets complexes
Vous pouvez utiliser le tri par insertion pour trier des objets complexes en fonction d’une clé spécifique.
function trierParNom(contacts) {
for (let i = 1; i < contacts.length; i++) {
let contactCourant = contacts[i];
let j = i - 1;
while (j >= 0 && contacts[j].nom > contactCourant.nom) {
contacts[j + 1] = contacts[j];
j--;
}
contacts[j + 1] = contactCourant;
}
return contacts;
}
// Exemple d'utilisation
let contacts = [
{ nom: "Alice", age: 30 },
{ nom: "David", age: 25 },
{ nom: "Bob", age: 40 }
];
console.log("Contacts avant le tri :", contacts);
contacts = trierParNom(contacts);
console.log("Contacts après le tri par nom :", contacts);2. Tri avec une fonction de comparaison personnalisée
Vous pouvez rendre le tri par insertion plus flexible en permettant au développeur de fournir une fonction de comparaison personnalisée.
function trierAvecComparaison(tab, comparer) {
for (let i = 1; i < tab.length; i++) {
let valeurCourante = tab[i];
let j = i - 1;
while (j >= 0 && comparer(tab[j], valeurCourante) > 0) {
tab[j + 1] = tab[j];
j--;
}
tab[j + 1] = valeurCourante;
}
return tab;
}
// Exemple d'utilisation
let nombres = [5, 2, 10, 3, 8];
console.log("Nombres avant le tri :", nombres);
nombres = trierAvecComparaison(nombres, (a, b) => a - b);
console.log("Nombres après le tri croissant :", nombres);
nombres = trierAvecComparaison(nombres, (a, b) => b - a);
console.log("Nombres après le tri décroissant :", nombres);3. Tri avec des données en temps réel
Vous pouvez utiliser le tri par insertion pour trier des données en temps réel dans une application Web.
// Fonction pour mettre à jour l'affichage en fonction des données triées
function mettreAJourAffichage(tableauTrié) {
// Mettre à jour l'affichage en utilisant le tableau trié
}
// Fonction pour ajouter une nouvelle donnée et la trier dans le tableau existant
function ajouterDonneeEnTempsReel(nouvelleDonnee, tableauTrié) {
tableauTrié.push(nouvelleDonnee);
triInsertion(tableauTrié);
mettreAJourAffichage(tableauTrié);
}
// Exemple d'utilisation
let tableauTrié = [3, 6, 9, 12];
ajouterDonneeEnTempsReel(7, tableauTrié);Ces exemples montrent comment le tri par insertion peut être utilisé de manière avancée dans différentes situations pour trier des données de manière efficace et flexible en JavaScript.
Conclusion
Le tri par insertion est un algorithme simple mais efficace pour trier des données. Bien qu’il ne soit pas aussi rapide que certains des algorithmes de tri plus avancés, le tri par insertion reste pertinent dans certaines situations. Notamment lorsque la taille des données est petite ou lorsque le tableau est déjà presque trié. En comprenant ses principes et en évaluant ses avantages et inconvénients, les développeurs peuvent choisir judicieusement entre le tri par insertion et d’autres algorithmes de tri en fonction des besoins spécifiques de leur application.
Autres articles
