L’algorithme de comparaison de chaînes lexicographiques fonctionne très simplement : les codes de caractères sont comparés en boucle et le résultat est renvoyé si les caractères ne sont pas égaux.
Un exemple pour le langage C peut être trouvé ici :
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c
Il convient de prendre en compte le fait que vous devez comparer les caractères dans un seul encodage statique, par exemple dans Swift, j’ai utilisé la comparaison caractère par caractère en UTF-32. L’option de tri de tableau utilisant memcmp fonctionnera exactement pour les caractères à un octet, dans d’autres cas (codages de longueur variable), l’ordre peut être incorrect. Je n’exclus pas la possibilité d’une implémentation basée sur des encodages de longueur variable, mais ce sera très probablement un ordre de grandeur plus compliqué.
La complexité temporelle de l’algorithme est O(1) dans le meilleur des cas, O(n) dans la moyenne et le pire des cas
Sources
https://ru.wikipedia.org/wiki/Lexicographic_order
Sources
https://gitlab.com/demensdeum /algorithms/blob/master/lexiCompare/lexiCompare.swift