Un tri JavaScript non stable peut-il devenir stable ?

Tri stable en JavaScript avec une touche

Le tri d'une collection d'objets est une tâche courante en programmation, nécessitant souvent de la stabilité pour préserver l'original ordre des éléments égaux. Cependant, la stabilité peut ne pas être inhérente à l'algorithme de tri utilisé.

Introduire un tri stable et non stable

Une approche surprenante mais efficace consiste à transformer un tri non stable fonctionner en un système stable. Avant le tri, les positions de tous les éléments sont obtenues. La condition de tri est modifiée pour considérer à la fois la clé primaire et la position d'origine de l'élément comme clé secondaire.

En utilisant la position comme critère de départage en comparaison, la stabilité du résultat final trié est assurée.

Implémentation en JavaScript

L'extrait ci-dessous fournit un exemple d'implémentation en JavaScript :

<code class="javascript">function stableSort(array, key) {
  const positions = [];

  for (let i = 0; i < array.length; i++) {
    positions[i] = i;
  }

  array.sort((a, b) => {
    const keyComparison = a[key].localeCompare(b[key]);
    return keyComparison || positions[a] - positions[b];
  });
}</code>

Dans ce code, la fonction stableSort trie le tableau selon le spécifié clé de manière stable. Le tableau positions capture les positions initiales des éléments. La condition de tri s'appuie sur localeCompare pour les comparaisons de chaînes et revient à la comparaison de position comme critère de départage.

Cette approche offre la flexibilité nécessaire pour exploiter tout algorithme de tri non stable tout en maintenant la stabilité pour des éléments égaux.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!