¿Cómo implementar un algoritmo de ordenación natural en c ++?

Question

Estoy ordenando cadenas que están formadas por texto y números. Quiero que la ordenación ordene las partes numéricas como números, no alfanuméricos.

Por ejemplo, quiero: abc1def, ..., abc9def, abc10def

en lugar de: abc10def, abc1def, ..., abc9def

¿Alguien conoce un algoritmo para esto (en particular en c ++)

Gracias

Answer 1

Le pregunté a esta pregunta exacta (aunque en Java) y me señalaron http://www.davekoelle.com/alphanum.html que tiene un algoritmo e implementaciones en muchos idiomas.

Answer 2

Esto se conoce como clasificación natural. Hay un algoritmo aquí que parece prometedor.

Tenga cuidado con los problemas con caracteres no ASCII (consulte Jeff's entrada de blog sobre el tema).

Answer 3

Hay disponibles varias implementaciones de ordenamiento natural para C ++. Una breve reseña:

• natural_sort<> - basado en Boost.Regex.
  • En mis pruebas, es aproximadamente 20 veces más lento que otras opciones.
• Dirk Jagdmann's alnum.hpp , basado en algoritmo alfanumérico
  • Posibles problemas de exceso de números enteros para valores superiores a MAXINT
• Martin Pool's natsort - escrito en C, pero trivialmente utilizable desde C ++.
  • La única implementación de C / C ++ que he visto ofrece una versión que no distingue entre mayúsculas y minúsculas, lo que parece ser una alta prioridad para un " natural " ordenar.
  • Al igual que las otras implementaciones, en realidad no analiza los puntos decimales, pero hace ceros iniciales en mayúsculas y minúsculas (se supone que cualquier cosa con un 0 inicial es una fracción), lo cual es un poco extraño pero potencialmente útil.
  • PHP usa este algoritmo.

Answer 4

Volver a publicar parcialmente mi otra respuesta :

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() función:

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

Uso:

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

Answer 5

Para resolver lo que es esencialmente un problema de análisis de una máquina de estados (también conocido como autómata de estados finitos ) es el camino a seguir. Insatisfecho con las soluciones anteriores, escribí un algoritmo simple de rescate inicial de una pasada que supera las variantes de C / C ++ sugeridas anteriormente en términos de rendimiento, no sufre errores de desbordamiento de tipo de datos numéricos y es fácil de modificar para agregar insensibilidad al caso si es necesario .

Se pueden encontrar

fuentes aquí

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;
}

No estoy muy seguro si es lo que quieres, de todos modos, puedes intentarlo :-)