Comment utiliser le tri par distribution (tri par base, etc.) pour trier les chaînes ?

Question

Je sais comment utiliser le tri par base pour trier des entiers.

Mais comment l’utiliser pour trier des chaînes ?ou des nombres flottants ?

Answer 1

Le tri par base ou tout autre tri par distribution peut être utilisé pour trier les nombres à virgule flottante si vous en ignorez certaines particularités comme l'infini, les valeurs non numériques et deux représentations différentes de zéro. IEEE 754-2008 les nombres à virgule flottante ont des représentations binaires, compatibles dans l'ordre de tri avec les nombres entiers.Donc, si vous excluez les nombres non-nombres et réinterprétez float ou double comme int32 ou int64, vous pouvez leur appliquer directement n'importe quel tri de distribution. Modifier: Les nombres à virgule flottante négatifs nécessitent un traitement spécial (comme l'a souligné AShelly), car leur ordre de tri est opposé à l'ordre de tri des nombres entiers.

Avec les cordes, c'est plus difficile à cause de leur longueur variable.Un autre type de tri de distribution (tri par compartiment) peut être utilisé et est souvent utilisé pour les chaînes.Plusieurs caractères de début de la chaîne sont utilisés pour l'indexation des compartiments, puis tout tri comparatif est utilisé pour trier les chaînes à l'intérieur des compartiments.

Si toutes les chaînes ont presque la même longueur et/ou si une technique est utilisée pour amplifier les différences entre les chaînes (comme décrit au chapitre 6 de "RAPIDE:Recherche arborescente rapide et sensible à l'architecture sur les processeurs et GPU modernes »), alors le tri par base peut également être utilisé :divisez la chaîne en groupes de caractères (ou mieux, en groupes de bits) de longueur égale, réinterprètez ces groupes comme des entiers et continuez comme s'il s'agissait d'un tri par base pour les entiers.

Modifier: Tous les types de tri de distribution sont garantis de fonctionner correctement uniquement pour les chaînes ASCII.D'autres codages de chaînes peuvent nécessiter un ordre de tri différent ou dépendre du paramètre "collate" des paramètres régionaux.

Answer 2

Oui, c'est possible.

voir Tri radix, trier des données de flotteur pour les flotteurs.Il utilise le fait que les flotteurs lancés vers des types entiers comparent correctement (une fois que les négatifs sont corrigés pour).Voir Cet article pour plus de détails

Pour les chaînes, vous pouvez résoudre le problème de la longueur variable en effectuant une sorte de radix MSD et en vous assurant que vous arrêtez de descendre lorsque vous rencontrez des NULLS.Voir Tri radix implémenté dans C ++ pour chaîne .