cours - partie 4

†††††Æ†††Æ†††††Plan Tris > DéfinitionAlgorithme Données de base : une liste de n éléments.A chaque élément est associée une clé.Types abstraits de donnéesLes clés appartiennent à un ensemble sur Pointeurslequel on dispose d’un ordre total.Résultat : une liste dont les éléments sont Listesune permutation des éléments de la liste Pilesd’origine.FilesLes clés sont croissantes quand on parcourt la liste séquentielles (cas général des listes Tristriées) .Complexité01/09/2006 1 01/09/2006 2Tris > La sorte Clé Tris > La sorte CléSorte Clé Axiomes :x ≤ y= vraiUtilise Booléen( x ≤ y ) ∧ ( y ≤ x ) ⇒ x = yOpérations : ( x ≤ y ) ∧ ( y ≤ z ) ⇒ x ≤ z≤ : Clé ⊗ Clé Booléen ;On appelle clé l’application, qui à chaque Avec : éléments associe sa clé :x , y , z : Clé Clé: Elément Clé01/09/2006 3 01/09/2006 41„„†††††„†„†††„„„„†Tris > Tris internes et tris Tris > Tri stable externesTri interne : opère sur des données présentes en tri stable : conserve l’ordre d’origine des mémoire centrale.éléments dont les clés sont égales.Tri externe : opère sur des données appartenant àdes fichiers.Important en cas de tri multi-critères(multi-clés)Problème d’optimisation différents :En tri interne, on cherche à réduire le nombre de comparaison et de toutes les opérations internes. En tri externe, on s’intéresse aux comparaisons et surtout aux entrées sorties.01/09/2006 5 01/09/2006 6Tris > Tris itératifs > Tris par Tris > ...