EN

pcosmos.ca

l'univers de Philippe Choquette

Tri fusion

Tri fusion JavaScript

Pour trier une table html je voulais une procédure de tri stable.
Voici où je l'ai utilisée. Cliquer sur les titres des colonnes pour trier. Cliquer encore pour trier en ordre descendant.
Voici le script que j'ai écrit. La fonction lt_or_eq est personnalisée selon les différentes données présentes dans chaque colonne.


var desc=false;

function lt_or_eq(obj1, obj2)
{
   return (desc) ? obj1 >= obj2 : obj1 <= obj2;
}

function mergesort(arr)
{
   var left = new Array();
   var right = new Array();
   var len = arr.length;

   if (len <= 1) return arr;

   var middle = Math.floor(len / 2);
   for (var i = 0; i < middle; i++) left.push(arr[i]);
   for (var i = middle; i < len; i++) right.push(arr[i]);

   left = mergesort(left);
   right = mergesort(right);

   return merge(left, right);
}

function merge(left, right)
{
   var retval = new Array();
   while(left.length > 0 && right.length > 0)
   {
      if (lt_or_eq(left[0], right[0])) retval.push(left.shift());
      else retval.push(right.shift());
   }

   if (left.length > 0) return retval.concat(left);
   if (right.length > 0) return retval.concat(right);

   return retval;
}

Le code ci-haut est adéquat pour trier un tableau d'objets pour lesquels les opérateurs >= et <= vont donner un résultat pertinent. Pour trier en ordre descendant, changer la valeur de desc pour true.

J'ai trouvé la description du l'algorithme du tri fusion sur en.wikipedia.org.