Heap Sort / Tri par la Méthode du Tas 1. Principe
2. Algorithme
Procédure Descend (Element: Tableau; K, L: Entier) X <- Element (K) I <- K J <- 2*I SI J < L et Element (J+1) > Element (J) ALORS J <- J+1 FIN SI TANT QUE J <= L et Element (J) > X FAIRE Element (I) <- Element (J) I <- J J <- 2*I SI J < L et Element (J+1) > Element (J) ALORS J <- J+1 FIN SI FIN TANT QUE Element (I) <- X Fin Procédure Procédure HeapSort (Element : Tableau; N: Entier) POUR K ALLANT DE N/2 JUSQU'A 1 FAIRE Descend (Element, K, N) FIN POUR POUR K ALLANT DE N JUSQU'A 2 FAIRE X <- Element (K) Element (K) <- Element(1) Element (1) <- X Descend (Element, 1, K-1) FIN POUR Fin Procédure 4. Exemples
4. 1. PHP
function Descend (&$Element, &$K, &$L) { $X = $Element[$K]; $I = $K; $J = 2*$I; if (($J < $L) && ($Element[$J+1] > $Element[$J])) { $J = $J+1; } while (($J <= $L) && ($Element[$J] > $X)) { $Element[$I] = $Element [$J]; $I = $J; $J = 2*$I; if (($J < $L) && ($Element[$J+1] > $Element[$J])) { $J = $J+1; } } $Element[$I] = $X; } Function HeapSort (&$Element, &$N) for ($K=$N div 2;$K>=1;$K--) { Descend ($Element, $K, $N); } for ($K=$N;$K>=2;$K--) { $X = $Element[$K]; $Element[$K] = $Element[$1]; $Element[$1] = $X; Descend ($Element, 1, $K-1); } } |