Tri par casier

[Gratteur]

Je m'amusai a comparer différentes façons de trier une liste quand je suis tombé sur un os :

Code : Tout sélectionner

#nbelements = 10000

Global Dim tableauindex(#nbelements)
For k=1 To #nbelements
  tableauindex(k) = Random(#nbelements)
Next k

Structure evordre ; evordre.evordre()
  evenement.l
  y.l
EndStructure

Global NewList evordre.evordre()
Global NewList validite.evordre()

Procedure Trierevordre()
  Protected Dim tab(0), Dim ref(0), NewList temp(), max, compteur
  max = #nbelements
  Dim tab(max+1)
  Dim ref(max+1)
  ForEach evordre()
    If tab(evordre()\y) = 0
      AddElement(temp())
      ref(evordre()\y) = @temp()
    Else
      ChangeCurrentElement(temp(), ref(evordre()\y))
      AddElement(temp())
    EndIf
    temp() = evordre()\evenement
    tab(evordre()\y)+1
  Next
  Debug "tri"
  ResetList(evordre()) 
  For k=0 To max
    If tab(k) > 0
      ChangeCurrentElement(temp(), ref(k))
      Repeat
        NextElement(evordre())
        evordre()\evenement = temp()
        evordre()\y = k
        NextElement(temp())
        tab(k)-1
        compteur+1
      Until tab(k) = 0
    EndIf
  Next k
EndProcedure

;Debug "Debut"
For k=1 To #nbelements
  AddElement(evordre())
  evordre()\evenement = k
  evordre()\y = tableauindex(k)
  ;Debug evordre()\y
Next k

t = ElapsedMilliseconds()
SortStructuredList(evordre(), 0, OffsetOf(evordre\y), #PB_Sort_Long)
Debug "Test 1 - Trié en :"+Str(ElapsedMilliseconds()-t)+ "ms"

t = ElapsedMilliseconds()
SortStructuredList(evordre(), 0, OffsetOf(evordre\y), #PB_Sort_Long)
Debug "Test 1' - Trié en :"+Str(ElapsedMilliseconds()-t)+ "ms"

;Sauvegarde des valeurs
ForEach evordre()
  AddElement(validite())
  validite()\evenement = evordre()\evenement
  validite()\y = evordre()\y
Next

ClearList(evordre())

For k=1 To #nbelements
  AddElement(evordre())
  evordre()\evenement = k
  evordre()\y = tableauindex(k)
Next k

t = ElapsedMilliseconds()
Trierevordre()
Debug "Test 2 - Trié en :"+Str(ElapsedMilliseconds()-t)+ "ms"

t = ElapsedMilliseconds()
Trierevordre()
Debug "Test 2' - Trié en :"+Str(ElapsedMilliseconds()-t)+ "ms"

;Debug "Resultat"
;ForEach evordre()
;  Debug evordre()\evenement
;Next

; Controle de validité
FirstElement(validite())
ForEach evordre()
  If validite()\y <> evordre()\y
    erreur = #True
    Break
  EndIf
  NextElement(validite())
Next

If erreur
  Debug "Tri erreur"
Else
  Debug "Tri ok"
EndIf

For k=1 To #nbelements
  v = #False
  ForEach evordre()
    If evordre()\evenement = k
      v = #True
      Break
    EndIf
  Next
  If v = #False
    erreurev = #True
    Break
  EndIf
Next k

If erreurev
  Debug "Evenement erreur"
Else
  Debug "Evenement ok"
EndIf

La procédure Trierevordre() devrait me réassocier les numéros d'événements après le

Code : Tout sélectionner

Debug "tri"

, mais apparament elle ne le fait pas tout le temps.
J'ai l'impression que l'erreur vient de la liste temp()

Quelqu'un aurait-il la bienveillance de regarder ça ? (en évitant les remarque désobligeants du style utiliser les fonctions sort de purebasic)

[Gratteur]

Et pour ceux que ça interesse voici un exemple de tri par casier :

Code : Tout sélectionner

#nbelements = 100000

Global Dim tableauindex(#nbelements)
For k=1 To #nbelements
  tableauindex(k) = Random(#nbelements)
Next k

Global NewList list()
Global NewList validite()

Procedure Trier()
  Protected Dim tab(0), min, max, longueur, longueur2, compteur
  longueur = CountList(list())
  FirstElement(list())
  min = list()
  max = min
  While NextElement(list())
    If list() < min
      min = list()
    EndIf
    If list() > max
      max = list()
    EndIf
  Wend
  longueur2 = max-min+1
  Dim tab(longueur2)
  ForEach list()
    tab(list()-min)+1
  Next
  ResetList(list()) 
  For i=0 To longueur2-1
    While tab(i) > 0
      NextElement(list())
      list() = (min+i)
      tab(i)-1
      compteur+1
    Wend
  Next i
EndProcedure

For k=1 To #nbelements
  AddElement(list())
  list() = tableauindex(k)
Next k

t = ElapsedMilliseconds()
SortList(list(), 0)
Debug "Test 1 - Classé en :"+Str(ElapsedMilliseconds()-t)+ "ms"

t = ElapsedMilliseconds()
SortList(list(), 0)
Debug "Test 1' - Classé en :"+Str(ElapsedMilliseconds()-t)+ "ms"

;Sauvegarde des valeurs
ForEach list()
  AddElement(validite())
  validite() = list()
Next

ClearList(list())

For k=1 To #nbelements
  AddElement(list())
  list() = tableauindex(k)
Next k

t = ElapsedMilliseconds()
Trier()
Debug "Test 2 - Classé en :"+Str(ElapsedMilliseconds()-t)+ "ms"

t = ElapsedMilliseconds()
Trier()
Debug "Test 2' - Classé en :"+Str(ElapsedMilliseconds()-t)+ "ms"

;Debug "Resultat"
;ForEach evordre()
;  Debug evordre()\y
;Next

; Controle de validité
FirstElement(validite())
ForEach list()
  If validite() <> list()
    erreur = #True
    Break
  EndIf
  NextElement(validite())
Next

If erreur
  Debug "Erreur"
Else
  Debug "Tris ok"
EndIf