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.
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.
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);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.
Voici comment vous pourriez mettre en œuvre ces exemples avec du code JavaScript utilisant le tri par insertion :
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);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);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 :
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é);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);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);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;
}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 :
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);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);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.
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.
L'histoire de nombreuses découvertes scientifiques récentes s'écrit dans des laboratoires où l'œil humain ne voit…
Parmi les différentes configurations de chromatographie liquide haute performance, la HPLC couplée à un détecteur…
Une analyse HPLC produit rarement un chiffre directement exploitable. Avant d'obtenir une concentration, une conformité…
Dans un laboratoire de contrôle qualité, certains équipements attirent immédiatement l'attention. Les balances analytiques, les…
Lorsqu'un laboratoire doit vérifier la teneur d'un médicament, rechercher une impureté ou confirmer l'identité d'une…
Téléchargez notre modèle Excel de validation HPLC automatisé conçu pour faciliter l'évaluation de la linéarité,…
This website uses cookies.