Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Tri par tas

Aller en bas 
AuteurMessage
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Tri par tas   Jeu 30 Aoû - 17:57

Principe :
- Construire un tas contenant les n éléments par adjonction successives ; en O (n log n).

- Tant que le tas n’est pas vide, faire supprimer le minimum du tas avec réorganisation, mettre ce minimum à sa place définitive ; en O (n log n).

La complexité en comparaison est au pire en O(n log n).

On utilise un seul tableau pour le tas et les valeurs des minimums successifs. Le minimum à récupérer est toujours dans t[1]. On mettra les minimums successifs à la droite du tableau, de la droite vers la gauche. à la fin, on obtient l’ensemble dans l’ordre décroissant.



Code:
Procédure triTAS (t : tableau)
var p, min : entiers
début
p <- 0
tant que p < n  faire
  ajouter( t , p , t[p+1] )
      tant que p > 1  faire
        suppress_min ( t , p , min )
        t[p+1] <- min
      fin tant que
fin tant que
fin
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
 
Tri par tas
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Cours-
Sauter vers: