Tri par base ou radix [Résolu]

Messages postés
152
Date d'inscription
jeudi 22 novembre 2007
Statut
Membre
Dernière intervention
21 mars 2016
- - Dernière réponse : f0xi
Messages postés
4200
Date d'inscription
samedi 16 octobre 2004
Statut
Modérateur
Dernière intervention
2 janvier 2019
- 30 janv. 2008 à 00:08
Bonjour à tous,

Je souhaite développer un algorithme de tri par base, ou tri radix. En effet, d'après ce que j'ai lu, il semble assez performant. Mais par contre, je vais vite peiner, et pas forcément au niveau de l'algorithme en lui-même. Je vous explique brièvement le principe de ce tri, puis mon problème.

Son mode opératoire est :

<ol><li>prend le chiffre (ou groupe de bits) le moins significatif de chaque clef,
</li><li>trie la liste des éléments selon ce chiffre, mais conserve l'ordre des éléments ayant le même chiffre (ce qui est un tri stable).
</li><li>répète le tri avec chaque chiffre plus significatif. </li></ol>exmple sur la liste : 170, 45, 75, 90, 2, 24, 802, 66
  tri par le chiffre le moins significatif (unités) :
170, 90, 2, 802, 24, 45, 75, 66
  tri par le chiffre suivant (dizaines) :
2, 802, 24, 45, 66, 170, 75, 90
  tri par le chiffre le plus significatif (centaines) :
2, 24, 45, 66, 75, 90, 170, 802

copié-collé de http://fr.wikipedia.org/wiki/Tri_par_base

Je compte travailler sur des entiers du type SmallInt (de -32768 à 32767). Ce que je ne vois pas comment faire, c'est considérer le chiffre des unités, puis des dizaines, ..., ou les 4 premiers bits, puis les 4 suivants, ... pour chacun de mes nombre à classe.

Merci pour votre prochaine aide.
Si c'est trop complexe, je me rabattrai sur un traditionnel QuickSort
Afficher la suite 

1 réponse

Messages postés
4200
Date d'inscription
samedi 16 octobre 2004
Statut
Modérateur
Dernière intervention
2 janvier 2019
26
0
Merci
chiffre des unités :

U = N mod 10
>> 2 = 512 mod 10

chiffre des dizaines :

D = (N div 10) mod 10

chiffre des centaines :

C = (N div 100) mod 10

etc ...

les quatres premiers bits (0 a 3) :

B0t3 = N and $F

les quatres suivant (4 a 7) :

B4t7 = (N shr 4) and $F

les quatres suivant (8 a 11) :

B8t11 = (N shr 8) and $F

etc ...

un hacheur par and logique :

type
  TMixator32 = array[0..3] of byte;

const
  MixatorLowMask  = $0f0f0f0f;
  MixatorHighMask = $f0f0f0f0;

var
  MxL,MxH : TMixator32;
  N  : longint;
begin

  MxL := TMixator32(N and MixatorLowMask);

  MxH := TMixator32(N and MixatorHighMask);

  // MxL[0] = bits 24 a 27

  // MxL[1] = bits 16 a 19

  // MxL[2] = bits 8 a 11

  // MxL[3] = bits 0 a 3

  // MxH[0] = bits 18 a 31

  // MxH[1] = bits 20 a 23

  // MxH[2] = bits 12 a 15

  // MxH[3] = bits 4 a 7
end;





si tu veux un quicksort, Florenth nous en avait poser un dans les sources, en plus prevus pour les entiers il me semble.





Commenter la réponse de f0xi