Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par tas
Un livre de Wikibooks.
Sections |
[modifier] C#
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); } } }
[modifier] Javascript
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>
[modifier] Pascal
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.
[modifier] PHP
// 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.
