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);
  }
}





Page modifiée le : 02/05/2022


Valid XHTML 1.0 Transitional