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.
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é.
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é.
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é);
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 :
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));
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));
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.
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);
}
}
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;
}
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.
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);
// 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);
// 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.
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
}
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);
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);
}
}
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.
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.
La méthode Thèse, Antithèse, Synthèse (TAS) est un outil incontournable pour structurer une dissertation, particulièrement…
1. Informations Générales Nom complet : Émile Édouard Charles Antoine Zola Date de naissance :…
1. Informations Générales Nom complet : Victor-Marie Hugo Date de naissance : 26 février 1802…
1. Informations Générales Nom complet : François Rabelais Date de naissance : Vers 1483 ou…
La modélisation financière est une pratique clé dans le domaine des finances et de la…
Un tableau de suivi des indicateurs est un outil essentiel pour mesurer la performance, suivre…
This website uses cookies.