forked from menault/TD4_DEV51_Qualite_Algo
21 lines
909 B
Plaintext
21 lines
909 B
Plaintext
A chaque niveau, on effectue des tris de taille M sur un certain nombre de tranches/blocs
|
|
|
|
|
|
Role de chaque fonction
|
|
|
|
ipow(a, b) : calcule a^b par multiplications successives.
|
|
|
|
cmp_int(a, b) : comparateur d'entiers pour qsort (retourne l'ordre).
|
|
|
|
reorder_blocks(base, block_sz, M, idx) : reordonne, dans un groupe de M blocs contigus de taille block_sz,
|
|
l'ordre des blocs selon le tableau d'indices idx (via un tampon temporaire).
|
|
|
|
sort_ND(a, N, M) :
|
|
- trie chaque sous-tableau 1D de longueur M (dimension la plus basse)
|
|
|
|
pour chaque niveau 2...N, calcule la somme de chaque bloc de la dimension inferieure, trie les blocs selon ces sommes, puis rerdonne physiquement les blocs.
|
|
|
|
Etant donne que notre parcours se fait sur le nombre d'element a parcourir dans chaque dimensions (c'est M), et que ce parcour on doit le faire sur chaque dimensions
|
|
On a donc M^N (M puissance N) comme complexite algorithmique.
|
|
|