tri par base ou radixRésolu

Question

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 :

prend le chiffre (ou groupe de bits) le moins significatif de chaque clef,
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).
répète le tri avec chaque chiffre plus significatif.

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

f0xi · Answer

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.

Tri par base ou radix

1 réponse

Votre réponse

Discussions similaires