Trie de tableaux à n colonnes
Publié : lun. 04/oct./2004 0:11
Un certain nombre de travaux existent sur le trie de tableaux à une colonne.
En revanche peu de choses le sont quant le nombre de colonnes du tableau augmente.
Aussi voici ce que j’ai bricolé à partir d’un des tries pour tableau à une colonne (voir http://purebasic.myforums.net/viewtopic ... =quicksort)
pour traiter le cas n colonnes.
L’algorithme est un QuickSort. Dans le code, il suffit de changer les valeurs xdim et ydim pour tester le trie sur un tableau de la taille souhaité.
Les arguments de la procédure sont les suivants :
QuickSort(*ptr, row.l, col.l, colmax.l)
avec,
*ptr : adresse du tableau array() à trier
row : jusqu’à quelle ligne du tableau array() doit etre fait le trie
col : colonne du tableau array() à trier
colmax: nombre total de colonne du tableau array()
D’autre part, pour bien fonctionner, la procédure nécessite la déclaration du tableau dummy()
Enfin, je vois trois axes d’améliorations à cette procédure :
1-Trouver le moyen d’incorporer la déclaration du tableau dummy() à la procédure
2-Ne procéder à la permutation de l’ensemble des colonnes qu’à la fin du trie --> le trie serait plus performant pour les tableaux à grand nombre de colonnes
3-Etendre la procedure de trie à tous les types de tableaux : Byte, Word, Float, String
En revanche peu de choses le sont quant le nombre de colonnes du tableau augmente.
Aussi voici ce que j’ai bricolé à partir d’un des tries pour tableau à une colonne (voir http://purebasic.myforums.net/viewtopic ... =quicksort)
pour traiter le cas n colonnes.
L’algorithme est un QuickSort. Dans le code, il suffit de changer les valeurs xdim et ydim pour tester le trie sur un tableau de la taille souhaité.
Les arguments de la procédure sont les suivants :
QuickSort(*ptr, row.l, col.l, colmax.l)
avec,
*ptr : adresse du tableau array() à trier
row : jusqu’à quelle ligne du tableau array() doit etre fait le trie
col : colonne du tableau array() à trier
colmax: nombre total de colonne du tableau array()
D’autre part, pour bien fonctionner, la procédure nécessite la déclaration du tableau dummy()
Enfin, je vois trois axes d’améliorations à cette procédure :
1-Trouver le moyen d’incorporer la déclaration du tableau dummy() à la procédure
2-Ne procéder à la permutation de l’ensemble des colonnes qu’à la fin du trie --> le trie serait plus performant pour les tableaux à grand nombre de colonnes
3-Etendre la procedure de trie à tous les types de tableaux : Byte, Word, Float, String
Code : Tout sélectionner
xdim =5
ydim =2
Dim dummy.l(0)
Dim array.l(xdim,ydim)
Procedure QuickSortRecursive(s.l, e.l, col.l, colmax.l)
i=s
j=e
k= col + (colmax+1)*((i+j)/2)
pivot=dummy(k)
Repeat
a = i+j
ki= col + (colmax+1)*i
While dummy(ki) < pivot
i = i+1
ki= col + (colmax+1)*i
Wend
a = i+j
kj= col + (colmax+1)*j
While dummy(kj) > pivot
j = j-1
kj= col + (colmax+1)*j
Wend
If i <= j
; Debug Str(i)+"/"+Str(j)
For k=0 To colmax
ki=k + (colmax+1)*i
kj=k + (colmax+1)*j
tmp = dummy(ki)
dummy(ki) = dummy(kj)
dummy(kj) = tmp
Next k
i = i+1
j = j-1
EndIf
Until i > j
If j > s : QuickSortRecursive(s,j, col, colmax) : EndIf
If i < e : QuickSortRecursive(i,e, col, colmax) : EndIf
EndProcedure
Procedure QuickSort(*ptr, row.l, col.b, colmax.b)
; *ptr: adress of the array to be sort
; row: row until the sort will be done
; col: colum of the sort
; colmax: total colum of the array to be sort
dummy() = *ptr
QuickSortRecursive(0, row, col, colmax)
EndProcedure
;
;
RandomSeed(0)
For i=0 To xdim
text$=""
array(i,0)=i+1
text$ = text$ + " " + Str(array(i,0))
For k=1 To ydim
array(i,k)=Random(ValF("2e9"))
text$ = text$ + " " + Str(array(i,k))
Next k
Debug text$
Next i
Debug "Start Sort"
start = GetTickCount_()
QuickSort(@array(),xdim, 1, ydim)
end1 = GetTickCount_() - start
Debug "End Sort"
For i=0 To xdim
text$=Str(array(i,0))
For k=1 To ydim
text$ = text$ + " " + Str(array(i,k))
Next k
Debug text$
Next i
Debug ""
Debug "QuickSort :"+Str(end1)+"ms"
)
