Tri par base ou radix [Résolu]

Messages postés
152
Date d'inscription
jeudi 22 novembre 2007
Dernière intervention
21 mars 2016
- - Dernière réponse : zwyx
Messages postés
152
Date d'inscription
jeudi 22 novembre 2007
Dernière intervention
21 mars 2016
- 30 janv. 2008 à 09:43
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 

Votre réponse

2 réponses

Messages postés
4304
Date d'inscription
samedi 16 octobre 2004
Dernière intervention
9 mars 2018
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
Messages postés
152
Date d'inscription
jeudi 22 novembre 2007
Dernière intervention
21 mars 2016
0
Merci
Mais c'est biensûr !
Les opéraions sur les entiers et les masques logiques !
Ca parait tellement simple quand on connait la solution.
Merci beaucoup f0xi.

Pour le QuickSort, j'ai effectivement déjà regardé le source de http://www.delphifr.com/codes/ALGORITHME-TRI-RAPIDE-QUICKSORT-IMPLEMENTATION-FACILE_34509.aspx. Il est vraiment top.

Une dernière question, pour appliquer la procédure de tri sur les valeurs d'un TStringGrid, vaut-il meiux, au regard des performances:
- lancer directement l'algorithme sur les valeurs contenues dans les cellules du tableau, ou
- copier les valeurs dans un tableau dynamique, trier, et recopier le tableau dynamique dans le TStringGrid ?

Je précise que mon TStringGrid pourra contenir quelques 1E5 ou 1E6 entiers.

Bonne journée
Commenter la réponse de zwyx

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.