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

/**
 *
 * 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;
}