Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par tas
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);
}
}
}
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>
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ée 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.
// 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.