TRI DE TABLEAU, ALGORITHME LES PLUS CONNUS IMPLÉMENTÉS (FUSION, QUICK, SHELL, SEDGE, MERGE)

---

Commentaire sur cette source (2)
Ajouter un commentaire et/ou une note

Suite à une discussion sur le forum,
j'ai implémenté ces algorithmes pour les comparer à celui du navigateur qui est sans
surprise bien meilleur sous Firefow, mais IE reserve des surprises.
Mais bon, cela dépend des collections à trier,
en plus j'ai mis un test sympa avec des courbes et des statistiques.
On peut définir la taille de la collection et si elle est aléatoire ou presque triée.
Bon, je l'accorde ca n'a qu'un intérêt pédagogique, mais c'est un intérêt.
Si quelqu'un trouve une optimisation... n'hésitait pas.
Cordialement,
Pierrick

/**
 *
 * Le tri par insertion est le tri le plus efficace sur des listes de petite taille. 
 * C'est pourquoi il est utilisé par d'autres méthodes comme le tri rapide (ou quicksort).
 * Il est d'autant plus rapide que les données sont déjà triées en partie dans le bon ordre.
 *
 * Le principe de ce tri est très simple: c'est le tri que toute personne utilise naturellement
 * quand elle a des dossiers (ou n'importe quoi d'autre) à classer.
 * On prend un dossier et on le met à sa place parmi les dossiers déjà triés.
 * Puis on recommence avec le dossier suivant.
 *
 * Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans l'ordre.
 * Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément qu'on considère.
 * Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré à sa place dans la partie déjà triée.
 * On peut aussi faire une recherche par dichotomie sur les tableaux.
 *
 * Une amélioration possible de ce tri, sensible pour les listes de plus de 15 éléments, est le tri de Shell.
 *
 */
Array.prototype.insort = function( cf ) {
    this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
    var	i, j;
	var	temp;

	for (i = 1; i < this.length; i++) {
		/* invariant:  array[0..i-1] is sorted */
		j = i;
		/* customization bug: SWAP is not used here */
		temp = this[j];
		while (j > 0 && this.cf(this[j-1], temp) > 0) {
			this[j] = this[j-1];
			j--;
		}
		this[j] = temp;
	}
    return this;
}

/**
 *
 * Le tri fusion est un algorithme de tri asymptotiquement optimal (complexité en O(nlogn) et consomme O(n) en mémoire).
 * Le tri repose sur le fait que pour fusionner deux listes/tableaux trié(e)s dont la somme des longueurs est n,
 * n-1 comparaisons au maximum sont nécessaires.
 * Cet algorithme n'opère pas en place : il a besoin d'une zone temporaire de données de même taille que les données ;
 * par ailleurs, pour des données en mémoire vive, il est en pratique sensiblement plus lent que d'autres algorithmes
 * asymptotiquement optimaux comme le tri par tas.
 *
 */
Array.prototype.sortF = function( cf ){
	var sortLength = 1, de1, de2, de3, i;
	this.tmp = [];
	this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
    while(sortLength < this.length)
    {
    	de1 = 0;
    	while(de1 < this.length)
        {
                de2 = de1 + sortLength;
                de3 = de2 + sortLength;
                if(de2>this.length) de2 = this.length;
                if(de3>this.length) de3 = this.length;
                
                this._fusion(de1, de2-1, de2, de3-1, de3-de1, de1);
                de1 = de3;
        }
 
        for(i = 0 ; i < this.length ; i++){
         	this[i] = this.tmp[i];
        }
        
        sortLength *= 2;
    }
    return this;
};

Array.prototype._fusion = function(de1, vers1, de2, vers2, count, posInB)
{
	   for(var j = 0 ; j < count ; j++)
       {
			if(de2 > vers2)
		        this.tmp[posInB++] = this[de1++];
			else if(de1 > vers1)
		        this.tmp[posInB++] = this[de2++];
			else if(this.cf(this[de1], this[de2]) < 0)
		        this.tmp[posInB++] = this[de1++];
			else
				this.tmp[posInB++] = this[de2++];
       }
}

/**
 *
 * Le tri rapide (en anglais quicksort) est une méthode de tri inventée par C.A.R. Hoare en 1962 basée sur la méthode 
 * de conception diviser pour régner. Il peut être implémenté sur un tableau (tri sur place) ou sur des listes.
 * L'utilisation la plus répandue est tout de même sur des tableaux.
 * Il s'agit tout simplement de la méthode de tri sur place la plus rapide connue pour des données réparties
 * aléatoirement (complexité en n \ \log \ n ).
 * Mais pour des données qui sont déjà presque triées, cet algorithme n'est pas le meilleur, 
 * voire peut être lent (complexité en n2) si l'implémentation est malhabile (au niveau du choix du pivot).
 * Il vaudra mieux alors utiliser le tri par insertion ou l'algorithme Smoothsort.
 *
 */
Array.prototype.sortQ = function(cf, p, r) {
	var q;
	if( this.cf == null )
		this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
	if( typeof p == 'undefined' )
		p = 0;
	if( typeof r == 'undefined' )
		r = this.length;
	if(p<r) {
	        q = this._part(p, r);
	        this.sortQ(null, p, q);
	        this.sortQ(null, q+1, r);
	}
    return this;
}

Array.prototype.swap = function(i, j){
	var temp = this[i];
   	this[i] = this[j];
   	this[j] = temp;
}

Array.prototype.partial_quickersort = function(lower, upper){
    var	i, j;
    var	temp, pivot;
    /* 15 has been found empirically as the optimal cutoff value in 1996 */
	/* In 2006, with computers very different and much faster it was found
	 * to be a close tie between 15 and 16 */
    var CUTOFF = 15;

    if (upper - lower > CUTOFF) {
    	this.swap(lower, parseInt( (upper+lower)/2 ));
		i = lower;
		j = upper + 1;
		pivot = this[lower];
		while (1) {
		    /*
		     * ------------------------- NOTE --------------------------
		     * ignoring BIG NOTE above may lead to an infinite loop here
		     * ---------------------------------------------------------
		     */
		    do i++; while (this.cf(this[i], pivot) < 0);
		    do j--; while (this.cf(this[j], pivot) > 0);
		    if (j < i) break;
		    this.swap(i, j);
		}
		this.partial_quickersort (lower, j - 1);
		this.partial_quickersort (i, upper);
    }
}

Array.prototype.sedgeSort  = function( cf ){
	this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
    this.partial_quickersort(0, this.length - 1);
    this.insort();
    return this;
}

Array.prototype._part = function(p, r) {
	var pivot = this[p], i = p-1, j = r+1;
	var temp;
	while(true) {
	        do
	                j--;
	        while(this.cf( this[j], pivot) > 0);
	        do
	                i++;
	        while(this.cf( this[i], pivot) < 0);
	        if(i<j) {
	                temp = this[i];
	                this[i] = this[j];
	                this[j] = temp;
	        }
	        else
	          return j;
	}
	return j;
}

/**
 *
 * Le tri de Shell ou Shell Sort en anglais est un algorithme de tri.
 * C'est une amélioration notable du tri par insertion.
 * Il est facile de comprendre intuitivement comment fonctionne cet algorithme
 * mais il est difficile de calculer son temps d'exécution.
 * Le tri de Shell est une amélioration du tri par insertion en observant deux choses:

    * Le tri par insertion est efficace si la liste est à peu près triée.
    * Le tri par insertion est inefficace en moyenne car il ne déplace les valeurs que d'une position par instruction.

 * Le tri de Shell trie chaque liste d'éléments séparés de n positions chacun avec le tri par insertion.
 * L'algorithme effectue plusieurs fois cette opération en diminuant n jusqu'à n=1 ce qui équivaut à trier tous les éléments ensemble.
 * Le fait de commencer avec des éléments espacés permet de pallier à l'inconvénient,
 * tandis que lorsque l'on fait à la fin avec un espacement de 1, ce qui est en fait un tri par insertion ordinaire, on tire parti de l'avantage.
 *
 */
Array.prototype.sortS = function( cf ) {
    this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
    /*
     * gaps[] doit approximer une Série géométrique.
     * La sequence suivante est la meilleure connue en terme
     * de nombre moyen de comparaisons. voir:
     * http://www.research.att.com/~njas/sequences/A102549
     */
    var gaps = [1, 4, 10, 23, 57, 132, 301, 701];
   
    for(var sizeIndex = gaps.length - 1; sizeIndex >= 0; --sizeIndex){
   		var gap = gaps[ sizeIndex ];
	    for (var i = gap; i < this.length; ++i) {
	        var value = this[i];
	        for (var j = i - gap; j >= 0 && this.cf(this[j], value) > 0; j -= gap) {
	            this[j + gap] = this[j];
	        }
	        this[j + gap] = value;
	    }           
    }
    return this;
}

Array.prototype.mergeSort = function(cf, lo, hi){
    if( this.cf == null )
		this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
	if( typeof lo == 'undefined' )
		lo = 0;
	if( typeof hi == 'undefined' )
		hi = this.length;
    // Base case
    if(lo == hi) {
      return this;
    }

    // Recurse
    var length = hi-lo+1;
    var pivot = parseInt( (lo+hi) / 2 );
    this.mergeSort(null, lo, pivot);
    this.mergeSort(null, pivot+1, hi);

    // Merge
    var working = [];
    for(var i = 0; i < length; i++)
      working[i] = this[lo+i];
    var m1 = 0;
    var m2 = pivot-lo+1;
    for(var i = 0; i < length; i++) {
      if(m2 <= hi-lo) {
	if(m1 <= pivot-lo) {
	  if(working[m1] > working[m2]) {
	    this[i+lo] = working[m2++];
	  }
	  else {
	    this[i+lo] = working[m1++];
	  }
	}
	else {
	  this[i+lo] = working[m2++];
	}
      }
      else {
	this[i+lo] = working[m1++];
      }
    }
    return this;
  }
  
  
/**
 * Make the sub-array starting at position i into a a heap,
 * assuming that it's left and right children are already 
 * heaps.
 */
Array.prototype.reheap = function(i){
	var done = false;
	var T = this[i];
	var parent = i;
	var child = 2*(i+1)-1;
	while ((child < this.length) && (!done)) {
	    if (child < this.length - 1) {
			if (this.cf( this[child], this[child + 1]) >= 0 ) {
			    child += 1;
			}
	    }
	    if (T < this[child]) {
			done = true;
	    }
	    else {
			this[parent] = this[child];
			parent = child;
			child = 2*(parent+1)-1;
	    }
	}
	this[parent] = T;
}

/**
 * Make the sub-array starting at position length-i into a a heap,
 * assuming that it's left and right children are already 
 * heaps.
 */
Array.prototype.invreheap = function(i){
	var done = false;
	var T = this[this.length - 1 - i];
	var parent = i;
	var child = 2*(i+1)-1;
	while ((child < this.length) && (!done)) {
	    if (child < length - 1) {
			if (this.cf( this[this.length - 1 - child], this[this.length - 1 - (child + 1)]) <= 0) {
			    child += 1;
			}
	    }
	    if (T > this[this.length - 1 - child]) {
			done = true;
	    }
	    else {
			this[this.length - 1 - parent] = this[this.length - 1 - child];
			parent = child;
			child = 2*(parent+1)-1;
	    }
	}
	this[this.length - 1 - parent] = T;
}

/**
 * Sort using the heap sort algorithm.
 */
Array.prototype.jSort = function( cf ){
	this.cf = typeof cf != 'undefined' ? cf : function (e1,e2){ return e1 < e2 ? -1 : e1 == e2 ? 0 : 1; };
	var i, j, T;
	// Heapify bottom up
	for (i = this.length-1; i >= 0; i--)
	    this.reheap(i);

	// Heapify top down
	for (i = this.length-1; i >= 0; i--)
	    this.invreheap (i);

	// Do an insertion sort on the almost sorted array
	this.insort( this.cf );
	return this;
}

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

09 août 2007 10:26:30 :

Ajout du tri par insertion optimisé. Ajout de l'algo Sedge, optimisation du quick sort par le tri par insertion.

09 août 2007 12:20:07 :

Ajout de l'algorithme mergeSort, bien meilleur sous IE que le sort natif, ajout de jSort pour la pédagogie. Conclusion: Sous FF et opéra, garder le sort natif. Sous IE pour les collection presque triée utiliser sedgeSort et pour les collections aléatoire utiliser medgeSort

09 août 2007 12:24:24 :

Ajout de l'algorithme mergeSort bien meilleure sous IE que la fonction native pour les collections aléatoires. Conclusion: Sous FF et Opéra utiliser la fonction native dans presque tous les cas. Sous IE utiliser sedgeSort pour les collections presue triées et mergeSort pour les collection aléatoires.

• PROGRESS BAR WIDGET
• DESSINER EN JS: LIGNES, FIGURES, ELLIPSES, ELLIPSES PLEINES,
• DÉMO TOOLTIPS AVEC LA WWT
• BOXMANAGEMENT: COMME LA PAGE D'ACCUEIL PERSONALISÉE DE GOOGLE
• THE WWT: WEB WIDGETS TOOLKIT

• LIST.ML D'OCAML EN JAVASCRIPT
• DIV APPARITION FUN
• JEU DE SOKOBAN
• CARRÉS MAGIQUES
• 8 AUTRES DAMES SUR UN ÉCHIQUIERS

• AFFICHAGE, ÉDITION GRAPHIQUE DE TABLEAUX
• TRI DE TABLEAUX HTML
• TRI DYNAMIQUE DE TABLEAU HTML, MULTI COLONNES, ORIENTÉ OBJET, IE ET FF
• TRI DE TABLEAU HTML, SCRIPT ORIENTÉ OBJET
• TRI MULTI-COLONNES D'UN TABLEAU HTML