Algorithmes de tri stables en JavaScript

Lors du tri de données, la préservation de l'ordre d'origine des éléments égaux est cruciale pour des algorithmes de tri stables. Dans ce contexte, nous visons à trier un tableau d'objets avec une clé spécifique dans un ordre donné tout en maintenant la cohérence de l'ordre des éléments.

Technique de tri stable

Fait intéressant, même les fonctions de tri non stables peuvent réaliser un tri stable. En capturant la position initiale de chaque élément avant le tri, nous pouvons rompre les liens dans la comparaison de tri en utilisant la position comme critère secondaire.

Implémentation en JavaScript

const sortBy = (arr, key, order) => {
  // Capture element positions
  const positions = arr.map((item, i) => {
    return { item, position: i };
  });

  // Perform sorting
  positions.sort((a, b) => {
    let cmp = a.item[key].localeCompare(b.item[key]);
    if (cmp === 0) {
      // Tiebreaker: sort by position
      cmp = a.position - b.position;
    }
    if (order === "desc") {
      return cmp * -1;
    } else {
      return cmp;
    }
  });

  // Return sorted objects
  return positions.map(position => position.item);
};

Exemple d'utilisation

const data = [
  { name: "Alice", age: 25 },
  { name: "Bob", age: 30 },
  { name: "Eve", age: 25 },
];

const sortedAscending = sortBy(data, "age", "asc");
console.log(sortedAscending); // [{ name: "Alice", age: 25 }, { name: "Eve", age: 25 }, { name: "Bob", age: 30 }]

const sortedDescending = sortBy(data, "age", "desc");
console.log(sortedDescending); // [{ name: "Bob", age: 30 }, { name: "Eve", age: 25 }, { name: "Alice", age: 25 }]

Cette technique permet un tri stable en JavaScript, préservant l'ordre d'origine des éléments avec des valeurs égales.