Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par tas

Un livre de Wikilivres.
Aller à : navigation, rechercher

C#[modifier | modifier le wikicode]

 
class Tri
    {
        private static void Echange(ref int a, ref int b)
        {
            int swap = a;
            a = b;
            b = swap;
        }
 
 
        private static void Tamiser(int[] arbre, int noeud, int n)
        {
            int k = noeud;
            int j = 2 * k;
 
            while (j <= n)
            {
                if ((j < n) && (arbre[j] < arbre[j + 1]))
                    j++;
 
                if (arbre[k] < arbre[j])
                {
                    Tri.Echange(ref arbre[k], ref arbre[j]);
                    k = j;
                    j = 2 * k;
                }
                else
                    break;
            }
        }
 
        public static void TriParTas(int[] arbre)
        {
            for (int i = arbre.Length >> 1; i >= 0; i--)
                Tri.Tamiser(arbre, i, arbre.Length - 1);
 
            for (int i = arbre.Length - 1; i >= 1; i--)
            {
                Tri.Echange(ref arbre[i], ref arbre[0]);
                Tri.Tamiser(arbre, 0, i - 1);
            }
        }
    }

Javascript[modifier | modifier le wikicode]

Voici un exemple complet. Un tableau d'entiers de composition aléatoire est créé et trié grâce à un tri par tas. Il suffit de copier tout ce code dans un fichier d'extension HTM puis de l'ouvrir dans un navigateur connecté à Internet. Le code du tri par tas est entièrement contenu dans le deuxième bloc SCRIPT.

<html>
<head>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.3.2/jquery.min.js"></script>
<script type="text/javascript">
 
    function echanger (arbre, a, b) {
        var temp = arbre[a];
        arbre[a] = arbre[b];
        arbre[b] = temp;
    }
 
 
    function tamiser (arbre, noeud, n) {
        var k = noeud;
        var j = 2 * k;
        while (j <= n) {
            if ((j < n) && (arbre[j] < arbre[j + 1]))
                j++;
            if (arbre[k] < arbre[j]) {
                echanger(arbre, k, j);
                k = j;
                j = 2 * k;
            } else
                break;
        }
    }
 
    function executer_tri_par_tas (arbre) {
        for (var i = arbre.length >> 1; i >= 0; i--)
            tamiser(arbre, i, arbre.length - 1);
        for (var i = arbre.length - 1; i >= 1; i--) {
            echanger(arbre, i, 0);
            tamiser(arbre, 0, i - 1);
        }
    }
 
</script>
<script type="text/javascript">
 
    $(document).ready(function() {
	var t = new Array();
	for (var indice = 0; indice < 100; indice++) t[indice] = Math.floor(Math.random() * 10000);
	afficher_tableau(t, "état initial :");
        executer_tri_par_tas(t);
	if (!verifier_si_tableau_est_trie(t)) {
		$("#infos").append("<br /><b>ERREUR ! LE TABLEAU FINAL N'EST PAS TRIE !</b><br />");
	} else {
		afficher_tableau(t, "état final :");
	}
    });
 
    function afficher_tableau (tableau, pre_string) {
	var s = "[ ";
	if (pre_string) s = pre_string + "<br />" + s;
	for (var i = 0, taille = tableau.length; i < taille - 1; i++) {
		s += tableau[i] + ", ";
	}
	s += tableau[taille - 1] + " ]";
	$("#infos").append(s + "<br />");
    }
 
    function verifier_si_tableau_est_trie (tableau) {
	var i = 1;
	var taille = tableau.length;
	while (i < taille) {
		if (tableau[i-1] > tableau[i]) return false;
		i++;
	}
	return true;
    }
 
</script>
</head>
<body style="font-size: 0.9em; background: #f6f6f6">
<div id="infos"></div>
</body>
</html>

Pascal[modifier | modifier le wikicode]

        uses wincrt;
        const Max = 100;
        type tab= array[1..Max] of integer;
 
        procedure Fill(var T : tab; n : integer);
        var i : integer;
        begin
        randomize;
                  for i:=1 to n do
                  t[i] := random(n);
        end;
 
        procedure Show(var T : tab; n : integer);
        var i : integer;
        begin
             for i:=1 to n do
             write(t[i],' ');
        writeln;
        end;
 
        procedure Permut(var x : integer; var y : integer);
        var inter : integer;
        begin
        inter := x;
        x := y;
        y := inter;
        end; 
 
        procedure TriTasCroissant(var t : tab; n : integer);
        var i , j , HeapSize : integer;
        begin
             for i:=1 to n do
             begin
             j := i;
             {la séquence t[1], ... t[i-1] est considéré comme un tas
             remonter t[i] dans sa bonne place ==> t[1],..t[i] }
                      while((j div 2> 0)and(t[j div 2] < t[j]))do
                      begin
                      Permut(t[j], t[j div 2]);
                      j := j div 2;
                      end;
             end;
             for i:=1 to n do
             begin
             HeapSize := n-i+1;
             Permut(t[1],t[HeapSize]);
             j := 1;
                    while( (2*j < HeapSize)and ( (t[2*j]  > t[j])or((2*j+1 < HeapSize)and(t[2*j+1] > t[j]))))do
                    begin
                         if((2*j+1 < HeapSize)and(t[2*j] < t[2*j+1]))then
                         begin
                         Permut(t[j],t[2*j+1]);
                         j := 2*j+1;
                         end
                         else
                         begin
                         Permut(t[j], t[2*j]);
                         j := 2*j;
                         end;
                    end;
             end;
    end;
 
    var t : tab;
 
    begin
    Fill(T,20);
    Show(T,20);
    TriTasCroissant(T,20);
    Show(T,20);
    end.

PHP[modifier | modifier le wikicode]

    // La procédure commencer() est facultative. Elle crée un tableau d'entiers $t de composition aléatoire
    // avant d'exécuter le tri par tas sur ce tableau. $t, bien qu'étant déclaré localement, est finalement
    // bien trié car il est transmis par référence aux procédures du tri.
 
    function echanger (&$arbre, $a, $b) {
        $temp = $arbre[$a];
        $arbre[$a] = $arbre[$b];
        $arbre[$b] = $temp;
    }
 
    function tamiser (&$arbre, $noeud, $n) {
        $k = $noeud;
        $j = 2 * $k;
        while ($j <= $n) {
            if (($j < $n) && ($arbre[$j] < $arbre[$j + 1]))
                $j++;
            if ($arbre[$k] < $arbre[$j]) {
                echanger($arbre, $k, $j);
                $k = $j;
                $j = 2 * $k;
            } else
                break;
        }
    }
 
    function executer_tri_par_tas (&$arbre) {
        for ($i = count($arbre) >> 1; $i >= 0; $i--)
            tamiser($arbre, $i, count($arbre) - 1);
        for ($i = count($arbre) - 1; $i >= 1; $i--) {
            echanger($arbre, $i, 0);
            tamiser($arbre, 0, $i - 1);
        }
    }
 
    function commencer () {
        $t = array();
        for ($indice = 0; $indice < 100; $indice++) $t[$indice] = floor(rand());
        executer_tri_par_tas($t);
    }
 
    commencer();

Tout ou partie de cette page est issue de l'article Wikipédia « Tri par tas » dans sa version du 23/05/2010.