Re: Coment trier un tableau structuré sur deux champs...
Publié : dim. 06/sept./2015 22:29
zen Falsam , brayane(dayvid) à fait des efforts, ne casse pas tout et revenons à l'essentiel.
Avec la méthode suivante qui n’utilise pas de zone supplémentaire malgré la notation en little-endian ou petit-boutistes ou mot de poids faible en tête. Par exemple, les processeurs x86 à l’adresse la plus faible on a le poids le plus faible et à l’adresse la plus forte on a le poids le plus fort.
La notation occidentale du nombre 4567 on lit 4 milles 5 cents soixante sept le poids fort est en tête nous sommes donc est en big-endian ou gros-boutistes ou mot de poids fort en tête, par exemple les processeurs Motorola 68000, les SPARC (Sun Microsystems) ou encore les System/370 (IBM).
Attention.
Dans un premier essai les nombres des deux champs sont positifs le résultat est correct.
Dans un deuxième essai le champ de poids fort peut être négatif le résultat est toujours correct.
Si vous essayez avec un troisième essai de placer des valeurs négatives dans le champ de poids faible le tri se fera comme s’il y avait une valeur positive dans ce champ.
Une petite remarque sur le tri stable comme falsam et Denis l’ont montré l’algo de tri de PB n’est pas stable au sens défini ci-dessous car s’il était stable on pourrait donner un ordre de tri sur chaque champs sans que l’ordre relatif du premier ait pu être modifié.
Caractère stable.
Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre.
Exemple, si on considère la suite d’éléments suivante :
(4, 1) (3, 2) (3, 3) (5, 4)
que l'on trie par rapport à leur première coordonnée (la clé), la seconde étant ici l'indice initial dans la suite, deux cas sont possibles, quand l’ordre relatif est respecté et quand il ne l'est pas :
(3, 2) (3, 3) (4, 1) (5, 4) (ordre relatif maintenu)
(3, 3) (3, 2) (4, 1) (5, 4) (ordre relatif changé)
Lorsque deux éléments sont égaux pour la relation d'ordre (c’est-à-dire qu'ils ont la même clé), l'algorithme de tri conserve l'ordre dans lequel ces deux éléments se trouvaient avant son exécution. Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stables, cependant cela peut être aux dépens de la rapidité et/ou peut nécessiter un espace mémoire supplémentaire.
Parmi les algorithmes listés plus bas, les tris étant stables sont : le tri à bulles, le tri par insertion et le tri fusion. Les autres algorithmes nécessitent O(n) mémoire supplémentaire pour stocker l'ordre initial des éléments.
Code : Tout sélectionner
Structure TESTi
Champs1.i
Champs2.i
EndStructure
Structure TESTx
StructureUnion
champs3.TESTi
champs4.q
EndStructureUnion
EndStructure
MAXT=200
Dim Tableau.Testx(MAXT)
For I = 0 To MAXT
; *** premier essai tous les champs sont positifs ****
Tableau(I)\champs3\Champs2 = Random(9, 0)
;**** deuxième essai le champ de poids fort peut être négatif *****
; Tableau(I)\champs3\Champs2 = Random(9, 0)*Pow(-1,Random(1,0)) ; permet de générer des nombres négatifs
Tableau(I)\champs3\Champs1= Random(1000, 100)
;**** Troisième essai le champ de poids faible peut être négatif
; Tableau(I)\champs3\Champs1= Random(1000, 100)*Pow(-1,Random(1,0)); permet de générer des nombres négatifs (valable en valeur absolue)
Next
SortStructuredArray(Tableau(), #PB_Sort_Ascending, OffsetOf(TESTx\champs4), #PB_Quad )
For I = 0 To MAXT
Debug Str(Tableau(I)\champs3\Champs2) + " - " + Str(Tableau(I)\champs3\Champs1) ;+ " - " + Str(tableau(i)\champs4) ; Commentaire à retirer si vous désirez voir la valeur du champ4 en xx.q
Next
. 
)
