Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Tri par tas

Voir le sujet précédent Voir le sujet suivant 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
Voir le sujet précédent Voir le sujet suivant 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: