¿Cómo implementar un algoritmo de ordenamiento natural en C++?

Question

Estoy ordenando cadenas compuestas de texto y números. Quiero ordenar las partes numéricas como números, no como alfanuméricos.

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

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

¿Alguien sabe un algoritmo para esto (en particular, en C++)

Gracias

Answer 1

He preguntado this exact question (although in Java) y he apuntado a http://www.davekoelle.com/alphanum.html que tiene un algoritmo y las implementaciones de la misma en muchos idiomas.

Answer 2

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

Tenga cuidado con los problemas con caracteres que no sean ASCII (consulte Jeff's blog entry sobre el tema).

Answer 3

// -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 quiere, de todos modos, usted puede tener una oportunidad :-)

Answer 4

Varias implementaciones ordenar natural para C++ están disponibles. Una breve reseña:

• natural_sort<> - basado en Boost.Regex.
  • En mis pruebas, es aproximadamente 20 veces más lento que otras opciones.
• de alnum.hpp Dirk Jagdmann, basado en alphanum algorithm
  • número entero Potencial de Dave Koelle overlow problemas para los valores más MAXINT
• de natsort Martin Pool - escrito en C, pero trivialmente utilizable a partir de C++.
  • La única implementación de C/C++ que he visto para ofrecer una versión insensible a las mayúsculas y minúsculas, que parece ser una alta prioridad para un tipo "natural".
  • Al igual que las otras implementaciones, en realidad no analiza los puntos decimales, pero tiene ceros a la izquierda de casos especiales (cualquier cosa con un 0 inicial se supone que es una fracción), que es un poco raro pero potencialmente útil.
  • PHP utiliza este algoritmo.

Answer 5

parcialmente volver a colocar my another answer:

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 6

Para resolver lo es esencialmente un problema de análisis una máquina de estado (aka finite state automaton) es el camino a seguir. Insatisfecho con las soluciones anteriores que he escrito un simple algoritmo temprana de rescate de una sola pasada que late C/C++ variantes sugerido anteriormente en términos de rendimiento, no sufre de los errores de tipo de datos de desbordamiento numérico, y es fácil de modificar para agregar mayúsculas y minúsculas, si es necesario .

fuentes se pueden encontrar here