Comment implémenter un algorithme de tri naturel en c ++?

Question

Je trie les chaînes composées de texte et de nombres. Je veux le tri pour trier les numéros sous forme de nombres et non alphanumériques.

Par exemple, je veux: abc1def, ..., abc9def, abc10def

au lieu de: abc10def, abc1def, ..., abc9def

Est-ce que quelqu'un connaît un algorithme pour cela (en particulier en c ++)

Merci

Answer 1

J'ai demandé à cette question exacte (bien qu'en Java) et a été pointé sur http://www.davekoelle.com/alphanum.html , qui a un algorithme et des implémentations dans de nombreuses langues.

Answer 2

C’est ce que l’on appelle le tri naturel. Il existe un algorithme ici que semble prometteur.

Faites attention aux problèmes liés aux caractères non-ASCII (voir de Jeff entrée de blog sur le sujet).

Answer 3

Plusieurs implémentations de tri naturel pour C ++ sont disponibles. Une brève revue:

• natural_sort<> - basé sur Boost.Regex.
  • Dans mes tests, il est environ 20 fois plus lent que les autres options.
• alnum.hpp de Dirk Jagdmann, d'après algorithme alphanum
  • Problèmes de débordement d'entiers potentiels pour les valeurs supérieures à MAXINT
• natsort de Martin Pool - écrit en C, mais utilisable trivialement à partir de C ++.
  • La seule implémentation C / C ++ que j'ai vue offre une version insensible à la casse, ce qui semble être une priorité élevée pour un & "naturel &"; trier.
  • Comme les autres implémentations, il n’analyse pas réellement les points décimaux, mais il fait des cas spéciaux précédant les zéros (tout ce qui porte un 0 devant est supposé être une fraction), ce qui est un peu étrange mais potentiellement utile.
  • PHP utilise cet algorithme.

Answer 4

Transfert partiel de autre réponse :

bool compareNat(const std::string& a, const std::string& b){
    if (a.empty())
        return true;
    if (b.empty())
        return false;
    if (std::isdigit(a[0]) && !std::isdigit(b[0]))
        return true;
    if (!std::isdigit(a[0]) && std::isdigit(b[0]))
        return false;
    if (!std::isdigit(a[0]) && !std::isdigit(b[0]))
    {
        if (a[0] == b[0])
            return compareNat(a.substr(1), b.substr(1));
        return (toUpper(a) < toUpper(b));
        //toUpper() is a function to convert a std::string to uppercase.
    }

    // Both strings begin with digit --> parse both numbers
    std::istringstream issa(a);
    std::istringstream issb(b);
    int ia, ib;
    issa >> ia;
    issb >> ib;
    if (ia != ib)
        return ia < ib;

    // Numbers are the same --> remove numbers and recurse
    std::string anew, bnew;
    std::getline(issa, anew);
    std::getline(issb, bnew);
    return (compareNat(anew, bnew));
}

toUpper() fonction:

std::string toUpper(std::string s){
    for(int i=0;i<(int)s.length();i++){s[i]=toupper(s[i]);}
    return s;
    }

Utilisation:

std::vector<std::string> str;
str.push_back("abc1def");
str.push_back("abc10def");
...
std::sort(str.begin(), str.end(), compareNat);

Answer 5

Pour résoudre ce qui est essentiellement un problème d'analyse syntaxique, une machine à états ( automate à états finis ) est le chemin à parcourir. Insatisfait des solutions ci-dessus, j’ai écrit un algorithme simple de sauvegarde anticipée en une passe, qui bat les variantes C / C ++ suggérées ci-dessus en termes de performances, ne souffre pas d’erreurs de débordement de types de données et est facile à modifier pour ajouter l’insensibilité à la casse si nécessaire .

Les

sources peuvent être trouvées ici

Answer 6

// -1: s0 < s1; 0: s0 == s1; 1: s0 > s1
static int numericCompare(const string &s0, const string &s1) {
    size_t i = 0, j = 0;
    for (; i < s0.size() && j < s1.size();) {
        string t0(1, s0[i++]);
        while (i < s0.size() && !(isdigit(t0[0]) ^ isdigit(s0[i]))) {
            t0.push_back(s0[i++]);
        }
        string t1(1, s1[j++]);
        while (j < s1.size() && !(isdigit(t1[0]) ^ isdigit(s1[j]))) {
            t1.push_back(s1[j++]);
        }
        if (isdigit(t0[0]) && isdigit(t1[0])) {
            size_t p0 = t0.find_first_not_of('0');
            size_t p1 = t1.find_first_not_of('0');
            t0 = p0 == string::npos ? "" : t0.substr(p0);
            t1 = p1 == string::npos ? "" : t1.substr(p1);
            if (t0.size() != t1.size()) {
                return t0.size() < t1.size() ? -1 : 1;
            }
        }
        if (t0 != t1) {
            return t0 < t1 ? -1 : 1;
        }
    }
    return i == s0.size() && j == s1.size() ? 0 : i != s0.size() ? 1 : -1;
}

Je ne sais pas si c'est ce que vous voulez, vous pouvez quand même essayer: -)