APPLICATIONSPROGRAMMATION ★ TRI PAR ARBORESCENCE ★

Tri Par Arborescence|CPC Revue)Applications Programmation

Le tri par arborescence découle directement de ia théorie des graphes dont nous rappelons quelques notions :

  • Un graphe est composé de sommets et d'arcs les reliant.
  • Une arborescence est un arbre dont chaque sommet (à l'exception du plus haut appelé racine) est l'extrémité terminale d'un seul arc.
  • Un noeud est un sommet qui est l'origine d'au moins un arc vers un sommet inférieur.
  • Les feuilles sont les derniers sommets qui ne dépendent d'aucun autre sommet.

Le tri par arborescence consiste à transformer la suite des informations du tableau à trier en une structure arborescente en générant les pointeurs de gauche, de droite et de sommet. Il comporte deux parties :

  • la création de l'arborescence qui consistera à mettre à jour les pointeurs en fonction de la c!é de tri. Le premier élément est pris pour racine et chaque élément suivant est mis à gauche s'il est plus petit et à droite s'il est plus grand, en mettant à jour les pointeurs "gauche", "droite" et "père" ;
  • la lecture de l'arborescence ainsi créée en partant de la feuille la plus à gauche qui sera l'élément le plus petit et en se servant des différents pointeurs pour
  • remonter.

Dans le programme, nous utilisons trois tableaux :

  • D$() le tableau à trier (alphanumérique dans notre cas),
  • R$() le tableau de résultats.
  • G() contiendra les pointeurs de gauche de l'élément.
  • D() contiendra les pointeurs de droite de l'élément.
  • PER() contiendra les pointeurs de sommet de l'élément.

Exemple : soit trier le tableau de la figure 1.


Fig. 1

Supposons que les 4 premiers éléments soient rangés en arborescence et proposons de ranger les deux suivants.

Ajoutons 4790

4790 est comparé à la racine 5320, il est plus petit et le pointeur gauche est non nul, on descend à gauche.
4790 est comparé à 4980, il est plus petit et le pointeur gauche est non nul, on descend à gauche.
4790 est comparé à 3870, il est plus grand et le pointeur droit est nul, on le met donc à droite.
On met le pointeur droit de 3870 à 5 et le père de 4790 à 4.

Ajoutons 6320

6320 est comparé à 5320, il est plus grand et le pointeur droit est non nul, on descend à droite. 6320 est comparé à 7490, il est plus petit et le pointeur gauche est nul, on le met donc à gauche. Le pointeur gauche de 7490 est mis à 6 et le père de 6320 est mis à 2.

Quant à l'efficacité de cette méthode, elle se rapproche de la méthode de Shell-Metzner (voir tableau) et est nettement plus performante que la méthode par dichotomie.

Nbre d'art.    30    150    300    600
Sélectio      3,9s    79s   295s
Dichotomie    3,9s    55s   194s
Shell-Metz    1,7s    18s  33,8s   86s
Arboresc.     1,7s    17s    38s  100s

CPC n°7

★ ÉDITEUR: CPC Revue
★ LICENCE: LISTING
★ ANNÉE: 1987
★ CONFIG: 64K + AMSDOS
★ LANGAGE:
★ AUTEUR: André COLLIN

★ AMSTRAD CPC ★ DOWNLOAD ★

Je participe au site:
» Newfile(s) upload/Envoye de fichier(s)
★ AMSTRAD CPC ★ A voir aussi sur CPCrulez , les sujets suivants pourront vous intéresser...

Lien(s):
» Applications » Pixel Editor
» Applications » Farbeneinsteller (CPC Amstrad International)
» Hardware » La Télématique du CPC ( A100%)
» Applications » Staticad (CPC Amstrad International)
» Applications » Dessin (CPC Infos)
» Applications » Z-Graph (Amstrad Especial)

QUE DIT LA LOI FRANÇAISE:

L'alinéa 8 de l'article L122-5 du Code de la propriété intellectuelle explique que « Lorsque l'œuvre a été divulguée, l'auteur ne peut interdire la reproduction d'une œuvre et sa représentation effectuées à des fins de conservation ou destinées à préserver les conditions de sa consultation à des fins de recherche ou détudes privées par des particuliers, dans les locaux de l'établissement et sur des terminaux dédiés par des bibliothèques accessibles au public, par des musées ou par des services d'archives, sous réserve que ceux-ci ne recherchent aucun avantage économique ou commercial ». Pas de problème donc pour nous!

CPCrulez[Content Management System] v8.75-desktop/c
Page créée en 082 millisecondes et consultée 735 fois

L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.