Coment trier un tableau structuré sur deux champs...

[G-Rom]

zen Falsam , brayane(dayvid) à fait des efforts, ne casse pas tout et revenons à l'essentiel.

[PAPIPP]

Bonjour à tous

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

A+

[Ollivier]

Bonjour PAPIPP,

cette explication et le code qui l'accompagne sont remerciables.

Je me permets d'ajouter très humblement que LSI ne disposait ni de l'outil "StructureUnion" ni de l'outil de tableau dynamique au sein des structures.

[Ollivier]

excellent, et mon code ? il marche mon code ? ou bien ?

Excellent aussi.
Chaque algo de tri a ses avantages et ses inconvénients.

[PAPIPP]

Bonjour à Tous

Denis nous montre avec ses essais, que le tri sur list est stable (au sens que j’ai nommé dans le post précédent) mais que le tri sur tableau n’est pas stable (Encore une petite incohérence dans PB)

Revenons à l’algo de falsam Denis et LSI et essayons cet algo avec des nombres négatifs

Les résultats sont conformes le signe – signe négatif des nombres place ceux-ci avant les valeurs positives mais continue à traiter les nombres comme des valeurs absolues.
Cet algo n’est pas correct pour aucun des deux champs négatifs.
en effet avec un ordre de tri ascendant -1 -2 -3 -4 -5 -6 -7 -8 -9 0 1 2 3 4 5 6 7 8 9 est l'ordre donné par l'algo
alors qu'il devrait être -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9

Code : Tout sélectionner

Structure TEST
	
	Cle.s
	
	Champs1.i
	Champs2.i
	
EndStructure
MAXT=200
Dim Tableau.Test(MAXT)

For I = 0 To MAXT
	Tableau(I)\Champs1 = Random(9, 0)*Pow(-1,Random(1,0)) ; permet de générer des nombres négatifs
	Tableau(I)\Champs2 = Random(1000, 100);*Pow(-1,Random(1,0)) ; permet de générer des nombres négatifs

	With Tableau(i)
		\Cle = Str(\Champs1) + RSet(Str(\Champs2), 6, "0")
	EndWith
Next

SortStructuredArray(Tableau(), #PB_Sort_Ascending, OffsetOf(TEST\Cle), #PB_String)

For I = 0 To MAXT
	Debug Str(Tableau(I)\Champs1) + " - " + Str(Tableau(I)\Champs2)
Next

A+

[Anonyme2]

Merci PAPIPP pour toutes ces précisions.

"L'algo" de LSI je l'utilise dans mon projet pour trier des icônes (dimension, profondeur etc.), je n'ai jamais à traiter de nombre négatifs, alors pour l'instant je garde .

C'est vrai que Fred (ou Freak) devrait peut-être améliorer les choses, voire proposer plusieurs types de tri avec une constante :
#PB_Sort_bulles, #PB_Sort_insertion , #PB_Sort_fusion ou d'autres, c'est juste pour soumettre l'idée.

[falsam]

Bonjour PAPIPP.

Revenons à l’algo de falsam Denis et LSI et essayons cet algo avec des nombres négatifs

Cet algo n’est pas correct pour aucun des deux champs négatifs.

La demande initiale de Brayane (sans faute) ne portant pas sur les nombres négatifs, j'ai effectivement procédé à un tri alpha et forcément ..... ça ne fonctionne pas avec les nombres négatifs.

Comment faire dans ce cas ?
On va faire un peu de bricolage en tenant compte que :
- la valeur maxi de Champ1 est égale à 9 signée (+ ou -) Max1.
- la valeur maxi de champ2 est égale à 1000 non signé Max2.

La clé de tri sera égale à Champ1 * Max1 * Max2 + Champ2 (J'espére que je ne me plante pas avec mon bricolage )

On procédera à un tri numérique (flag: #PB_Integer)

Le code

Code : Tout sélectionner

Declare RandomSign()

Structure Test
  Cle.i
  
  Champs1.i
  Champs2.i
  
EndStructure

Dim Tableau.Test(99)

For I = 0 To 99
  Tableau(I)\Champs1 = Random(9, 0) * RandomSign()
  Tableau(I)\Champs2 = Random(1000, 100)
  
  With Tableau(i)
    \Cle = \Champs1 * 9 * 1000  + \Champs2 
  EndWith
Next

SortStructuredArray(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Cle), #PB_Integer)

For I = 0 To 99
  Debug RSet(Str(Tableau(I)\Champs1), 3, " ") + "=> " + RSet(Str(Tableau(I)\Champs2), 4, "0")
Next


Procedure RandomSign()
  ProcedureReturn Random(1)*2-1
EndProcedure

Champ1 & Champ2 sont bien triées dans l'ordre ascendant.

[Micoute]

Mais c'est très bon ça ! J'adore ! Merci falsam pour ce partage.

[Brayane]

Merci PAPIPP pour toutes ces précisions.

"L'algo" de LSI je l'utilise dans mon projet pour trier des icônes (dimension, profondeur etc.), je n'ai jamais à traiter de nombre négatifs, alors pour l'instant je garde .

C'est vrai que Fred (ou Freak) devrait peut-être améliorer les choses, voire proposer plusieurs types de tri avec une constante :
#PB_Sort_bulles, #PB_Sort_insertion , #PB_Sort_fusion ou d'autres, c'est juste pour soumettre l'idée.

Je vote pour, c'est vraie que se serais vraiment cool d'avoir ça
Soumet l'idée si tu veux

[PAPIPP]

Bonjour falsam

Ce n’est pas du bricolage ce que tu as fait c’est réellement du codage.
Essayons d’optimiser ce codage.
Hypothèse 1)
Si le deuxième champ2 restait toujours positif
La fonction de codage suivant serait suffisante
Car il faut que la valeur
(1) pour Champ1>0 Champ1*k soit toujours supérieure à champ2
Pour Champ1<0 Champ1*k soit toujours inférieure à champ2
et pour cela il faut et il suffit que K soit égal au max de champ2 = MAX2
Donc Champ1*MAX2+champ2 codage ressemble à du décodage numérique classique.

Hypothèse 2)
Maintenant imaginons que champ2 puisse prendre des valeurs négatives
Dans un tri ascendant il faut que
(2) Champ1(n)*Max2+Champ2(n) soit => Champ1(N-1)*MAX2 + champ2(n-1)
Mais comme nous ne maitrisons pas champ2(n) et champ2(n-1) qui peuvent prendre des valeurs entre –MAX2 et +Max2
Nous pourrions avoir avec comme hypothèse Champ1(n)=Champ1(n-1)
ChAMP1(n)*MAX2-MAX2 < champ1(n-1)*MAX2+MAX2
Champ1(n)*MAX2-MAX2 <Champ1(n)*MAX2+MAX2 ce qui est contraire à la condition nécessaire à un tri correct
Il suffit donc de rendre champ2+Z toujours positif
Et comme Champ2 ne peut dépasser MAX2 ==>ajoutons MAX2+Champ2 =>0
Mais alors pour avoir un terme positif la valeur K à appliquer à Champ1 est doublée 2 *MAX2

Voici la formule de codage Pour vérifier les conditions (1) et (2) nous aurons
(3) Champ1*2*MAX2+MAX2+champ2

Le deuxième PB est que nous ne connaissons pas à priori la valeur MAX2
Pouvons-nous nous passer de cette valeur ;
Dans champ1.i la valeur maximum positive est $7FFFFFFF et $80000000 pour la maximum négative

Si nous portons ces valeurs dans l’équation (3)
Champ1*2* $7FFFFFFF+$7FFFFFFF+Champ2
Cette valeur ne peut être contenu dans clé.i en effet si Champ1 et Champ2 sont maximum nous aurons $7FFFFFFF*2*$7FFFFFFF+ $7FFFFFFF+ $7FFFFFFF
= 2*($7FFFFFFF*$7FFFFFFF)+2($7FFFFFFF) =9223372032559808512
est inférieure à Max de VAL.q = 9223372036854775807
il nous faut une clé.q
Voici le PRG

Code : Tout sélectionner

Declare RandomSign()

Structure TEST
	Cle.q
	Champs1.i
	Champs2.i
	
EndStructure
maxt=200
Dim Tableau.Test(MAXT)

For I = 0 To MAXT
	Tableau(I)\Champs1 = Random(9, 0) * RandomSign()
	Tableau(I)\Champs2 = Random(1000, 100)* RandomSign()
	
	With Tableau(i)
	  \Cle = \Champs1 * $7FFFFFFF*2+$7FFFFFFF + \Champs2 
	  

	EndWith
Next

SortStructuredArray(Tableau(), #PB_Sort_Ascending, OffsetOf(TEST\Cle), #PB_Quad)

For I = 0 To MAXT
	Debug RSet(Str(Tableau(I)\Champs1), 3, " ") + "=> " + RSet(Str(Tableau(I)\Champs2), 4, "0")+ " clé= " +Str(tableau(I)\Cle)
Next


Procedure RandomSign()
	ProcedureReturn Random(1)*2-1
EndProcedure

Ce prg permet de trier tous les nombres compris entre -2147483648 et +2147483647
A+

[falsam]

Jolie cette solution PAPIPP

[Anonyme2]

Merci PAPIPP pour la démonstration.

[PAPIPP]

Bonjour à Tous

Voila j’ai utilisé un tri bulle stable pour permettre de trier sur n’importe quel type de champ en tri ascendant ou descendant.
J’ai essayé de banaliser le module du tribulle. Il n’est pas encore complètement banalisé puisqu’il faut encore définir la structure utilisée dans le tableau lors de l’appel.

Toutefois on peut donner 1, 2, 3 champs ou plus au tri
Attention finissez toujours par le tri principal.

Code : Tout sélectionner

Structure TEST
  Nom.s
  Champs1.i
  Champs2.d
EndStructure
Global maxt=200
Procedure TRIBULLE(Array TAB.test(1),Offset,Type,ascdesc)
  
  Protected i,itemCount,hasChanged 
  itemCount=ArraySize(TAB())
  LongTerm=TAB(1)-TAB(0)
  
  *mem=AllocateMemory(Longterm, #PB_Memory_NoClear)
  
  Macro inverseterm
    CopyMemory(TAB(i), *Mem, LongTerm)
    CopyMemory(TAB(i+1), TAB(i), LongTerm)
    CopyMemory(*Mem, TAB(i+1), LongTerm)
    hasChanged = #True
  EndMacro
  itemCount=ArraySize(TAB())
  LongTerm=TAB(1)-TAB(0)
  
  Repeat
    hasChanged = #False
    itemCount - 1
    For i = 0 To itemCount
      Select ascdesc
       ;********************************  cas du tri ascendant ******************************         
    
        Case #PB_Sort_Ascending
          Select Type
            Case #PB_Byte    ; Le champ de la Structure est un octet (.b)
              If PeekB(tab(i)+offset)>PeekB(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_Word    ; Le champ de la Structure est un word (.w)
              If PeekW(tab(i)+offset)>PeekW(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_Long    ; Le champ de la Structure est un long (.l)
              If PeekL(tab(i)+offset)>PeekL(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_String  ; Le champ de la Structure est un string (.s ou $)
                             ; Les strings fixe (fixed strings) ne sont pas supportées)
                             ;           Resultat$ = PeekS(*Memoire [, Longueur [, Format]])
                             ;           Format
                             ;           #PB_Ascii  : Format ASCII.
                             ;           #PB_UTF8   : Format UTF-8.
                             ;           #PB_Unicode: Format Unicode.
                             ;     Par défaut ascii
              If PeekS(PeekL(tab(i)+offset))>PeekS(PeekL(tab(i+1)+offset))
                inverseterm 
              EndIf  
            Case #PB_Float    ; Le champ de la Structure est un flottant (.f)
              If PeekF(tab(i)+offset)>PeekF(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Double  ; Le champ de la Structure est un double (.d)
              If PeekD(tab(i)+offset)>PeekD(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Quad    ; Le champ de la Structure est un quad (.q)
              If PeekQ(tab(i)+offset)>PeekQ(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Character:; Le champ de la Structure est un caractère (.c)
              If PeekC(tab(i)+offset)>PeekC(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Integer ; Le champ de la Structure est un integer (.i)
              If PeekI(tab(i)+offset)>PeekI(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_Ascii   ; Le champ de la Structure est un caractère ascii (.a)
              If PeekA(tab(i)+offset)>PeekA(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Unicode ; Le champ de la Structure est un caractère unicode (.u)
              If PeekU(tab(i)+offset)>PeekU(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
          EndSelect 
 ;********************************  cas du tri descendant ******************************         
        Case #PB_Sort_Descending
          Select Type
            Case #PB_Byte    ; Le champ de la Structure est un octet (.b)
              If PeekB(tab(i)+offset)<PeekB(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_Word    ; Le champ de la Structure est un word (.w)
              If PeekW(tab(i)+offset)<PeekW(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_Long    ; Le champ de la Structure est un long (.l)
              If PeekL(tab(i)+offset)<PeekL(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_String  ; Le champ de la Structure est un string (.s ou $)
                             ; Les strings fixe (fixed strings) ne sont pas supportées)
                             ;           Resultat$ = PeekS(*Memoire [, Longueur [, Format]])
                             ;           Format
                             ;           #PB_Ascii  : Format ASCII.
                             ;           #PB_UTF8   : Format UTF-8.
                             ;           #PB_Unicode: Format Unicode.
                             ;     Par défaut ascii
              If PeekS(PeekL(tab(i)+offset))<PeekS(PeekL(tab(i+1)+offset))
                inverseterm 
              EndIf  
            Case #PB_Float    ; Le champ de la Structure est un flottant (.f)
              If PeekF(tab(i)+offset)<PeekF(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Double  ; Le champ de la Structure est un double (.d)
              If PeekD(tab(i)+offset)<PeekD(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Quad    ; Le champ de la Structure est un quad (.q)
              If PeekQ(tab(i)+offset)<PeekQ(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Character:; Le champ de la Structure est un caractère (.c)
              If PeekC(tab(i)+offset)<PeekC(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Integer ; Le champ de la Structure est un integer (.i)
              If PeekI(tab(i)+offset)<PeekI(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
            Case #PB_Ascii   ; Le champ de la Structure est un caractère ascii (.a)
              If PeekA(tab(i)+offset)<PeekA(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
            Case #PB_Unicode ; Le champ de la Structure est un caractère unicode (.u)
              If PeekU(tab(i)+offset)<PeekU(TAB(i + 1)+offset)
                inverseterm 
              EndIf  
              
          EndSelect
      EndSelect
      
    Next  
  Until hasChanged = #False
EndProcedure


Procedure RandomSign()
  ProcedureReturn Random(1)*2-1
EndProcedure

Dim Tableau.Test(MAXT)

For I = 0 To MAXT
  Tableau(I)\Champs1 = Random(9, 0) * RandomSign()
  Tableau(I)\Champs2 = Random(1000, 100)* RandomSign()
  tableau(i)\Nom="Dupond Pierre Jean Simon"+Str(Random(MAXt,0))
Next
; For I = 0 To MAXT
;   Debug RSet(Str(Tableau(I)\Champs1), 3, " ") + "=> " + RSet(Str(Tableau(I)\Champs2), 4, "0")+ "  "+tableau(I)\Nom
; Next
Debug "********************  Apès Tri"
TRIBULLE(tableau(),OffsetOf(test\Champs2),TypeOf(test\Champs2),#PB_Sort_Ascending)
TRIBULLE(tableau(),OffsetOf(test\Champs1),TypeOf(test\Champs1),#PB_Sort_Descending)
; TRIBULLE(tableau(),OffsetOf(test\Nom),TypeOf(test\Nom),#PB_Sort_Ascending)
; TRIBULLE(tableau(),OffsetOf(test\Nom),TypeOf(test\Nom),#PB_Sort_Descending)

; 
For I = 0 To MAXT
  Debug RSet(Str(Tableau(I)\Champs1), 3, " ") + "=> " + RSet(Str(Tableau(I)\Champs2), 4, "0") + "  "+tableau(I)\Nom
Next

A+

[Anonyme2]

Merci PAPIPP,

je mets cela dans mes modèle PB.

(je fais toujours des tests d'abord ... mon esprit suspicieux )

[Brayane]

Merci beaucoup PAPIPP
Jolie code