Algoritmo de ordenamiento natural

Question

¿Cómo se ordena una matriz de cadenas naturally en diferentes lenguajes de programación? Publique su implementación y en qué idioma se encuentra en la respuesta.

Answer 1

JavaScript

Array.prototype.alphanumSort = function(caseInsensitive) { 
    for (var z = 0, t; t = this[z]; z++) { 
    this[z] = [], x = 0, y = -1, n = 0, i, j; 

    while (i = (j = t.charAt(x++)).charCodeAt(0)) { 
     var m = (i == 46 || (i >=48 && i <= 57)); 
     if (m !== n) { 
     this[z][++y] = ""; 
     n = m; 
     } 
     this[z][y] += j; 
    } 
    } 

    this.sort(function(a, b) { 
    for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) { 
     if (caseInsensitive) { 
     aa = aa.toLowerCase(); 
     bb = bb.toLowerCase(); 
     } 
     if (aa !== bb) { 
     var c = Number(aa), d = Number(bb); 
     if (c == aa && d == bb) { 
      return c - d; 
     } else return (aa > bb) ? 1 : -1; 
     } 
    } 
    return a.length - b.length; 
    }); 

    for (var z = 0; z < this.length; z++) 
    this[z] = this[z].join(""); 
} 

Source

Answer 2

Para MySQL, yo personalmente uso de código de un módulo de Drupal, que está disponible en hhttp: //drupalcode.org/project/natsort.git/blob /refs/heads/5.x-1.x:/natsort.install.mysql

Básicamente, se ejecuta la secuencia de comandos SQL publicado para crear funciones, y luego usar ORDER BY natsort_canon(field_name, 'natural')

Aquí hay un readme acerca de la función: http://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/README.txt

Answer 3

Si el PO está preguntando por idiomáticas clasificación de expresiones, a continuación, no todas las lenguas tienen una expresión naturales construido en Para c Me gustaría ir a <stdlib.h> y uso qsort.. Algo en las líneas de:

/* non-functional mess deleted */ 

para ordenar los argumentos en orden léxico. Lamentablemente, este modismo es bastante difícil de analizar para aquellos que no utilizan las formas de c.

---

Adecuadamente castigado por el downvote, en realidad leer el artículo relacionado. Mea culpa.

En cualquier caso, el código original no funcionó, excepto en el caso único que probé. Maldita sea. Plain vanilla c no tiene esta función, ni está en ninguna de las bibliotecas habituales.

El código siguiente ordena los argumentos de la línea de comandos en el natural forma como vinculados. Caveat emptor ya que solo se ha probado ligeramente.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <ctype.h> 

int naturalstrcmp(const char **s1, const char **s2); 

int main(int argc, char **argv){ 
    /* Sort the command line arguments in place */ 
    qsort(&argv[1],argc-1,sizeof(char*), 
    (int(*)(const void *, const void *))naturalstrcmp); 

    while(--argc){ 
    printf("%s\n",(++argv)[0]); 
    }; 
} 

int naturalstrcmp(const char **s1p, const char **s2p){ 
    if ((NULL == s1p) || (NULL == *s1p)) { 
    if ((NULL == s2p) || (NULL == *s2p)) return 0; 
    return 1; 
    }; 
    if ((NULL == s2p) || (NULL == *s2p)) return -1; 

    const char *s1=*s1p; 
    const char *s2=*s2p; 

    do { 
    if (isdigit(s1[0]) && isdigit(s2[0])){ 
     /* Compare numbers as numbers */ 
     int c1 = strspn(s1,""); /* Could be more efficient here... */ 
     int c2 = strspn(s2,""); 
     if (c1 > c2) { 
    return 1; 
     } else if (c1 < c2) { 
    return -1; 
     }; 
     /* the digit strings have equal length, so compare digit by digit */ 
     while (c1--) { 
    if (s1[0] > s2[0]){ 
     return 1; 
    } else if (s1[0] < s2[0]){ 
     return -1; 
    }; 
    s1++; 
    s2++; 
     }; 
    } else if (s1[0] > s2[0]){ 
     return 1; 
    } else if (s1[0] < s2[0]){ 
     return -1; 
    }; 
    s1++; 
    s2++; 
    } while ((s1!='\0') || (s2!='\0')); 
    return 0; 
} 

Este enfoque es bastante fuerza bruta, pero es sencillo y, probablemente, se puede duplicar en cualquier lenguaje imperativo.

Answer 4

En C++ utilizo este example code para hacer la clasificación natural. El código requiere la biblioteca de impulso.

Answer 5

Acabo de usar StrCmpLogicalW. Hace exactamente lo que Jeff quiere, ya que es la misma API que usa el explorador. Es cierto que no es portátil.

En C++:

bool NaturalLess(const wstring &lhs, const wstring &rhs) 
{ 
    return StrCmpLogicalW(lhs.c_str(), rhs.c_str()) < 0; 
} 

vector<wstring> strings; 
// ... load the strings 
sort(strings.begin(), strings.end(), &NaturalLess); 

Answer 6

He aquí una limpieza de the code en the article la cuestión vinculada a:

def sorted_nicely(strings): 
    "Sort strings the way humans are said to expect." 
    return sorted(strings, key=natural_sort_key) 

def natural_sort_key(key): 
    import re 
    return [int(t) if t.isdigit() else t for t in re.split(r'(\d+)', key)] 

Pero en realidad no he tenido ocasión de resolver cualquier cosa de esta manera.

Answer 7

Así es como se puede obtener un comportamiento explorador-como en Python:

#!/usr/bin/env python 
""" 
>>> items = u'a1 a003 b2 a2 a10 1 10 20 2 c100'.split() 
>>> items.sort(explorer_cmp) 
>>> for s in items: 
...  print s, 
1 2 10 20 a1 a2 a003 a10 b2 c100 
>>> items.sort(key=natural_key, reverse=True) 
>>> for s in items: 
...  print s, 
c100 b2 a10 a003 a2 a1 20 10 2 1 
""" 
import re 

def natural_key(astr): 
    """See http://www.codinghorror.com/blog/archives/001018.html""" 
    return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', astr)] 

def natural_cmp(a, b): 
    return cmp(natural_key(a), natural_key(b)) 

try: # use explorer's comparison function if available 
    import ctypes 
    explorer_cmp = ctypes.windll.shlwapi.StrCmpLogicalW 
except (ImportError, AttributeError): 
    # not on Windows or old python version 
    explorer_cmp = natural_cmp   

if __name__ == '__main__': 
    import doctest; doctest.testmod() 

Para apoyar las cadenas Unicode, .isdecimal() deben utilizarse en lugar de .isdigit().

.isdigit() también pueden fallar (el valor de retorno no es aceptado por int()) para una cadena de bytes en Python 2 en algunas configuraciones regionales, por ejemplo, '\xb2' ('²') in cp1252 locale on Windows.

Answer 8

sólo un enlace a un trabajo agradable en Common Lisp por Eric Normand:

http://www.lispcast.com/wordpress/2007/12/human-order-sorting/

Answer 9

Para Tcl, la opción -dict (diccionario) a LSORT:

% lsort -dict {a b 1 c 2 d 13} 
1 2 13 a b c d 

Answer 10

Tenga en cuenta que para la mayoría de estas preguntas, puede consultar el Rosetta Code Wiki. Adapte mi respuesta de la entrada para ordenar enteros.

En el lenguaje de programación de un sistema, hacer algo como esto generalmente va a ser más feo que con un lenguaje de manejo de cadenas especial. Afortunadamente para Ada, la versión más reciente tiene una rutina de biblioteca para este tipo de tareas.

Para Ada 2005 creo que se podría hacer algo a lo largo de las siguientes líneas (de advertencia, no compilado!):

type String_Array is array(Natural range <>) of Ada.Strings.Unbounded.Unbounded_String; 
function "<" (L, R : Ada.Strings.Unbounded.Unbounded_String) return boolean is 
begin 
    --// Natural ordering predicate here. Sorry to cheat in this part, but 
    --// I don't exactly grok the requirement for "natural" ordering. Fill in 
    --// your proper code here. 
end "<"; 
procedure Sort is new Ada.Containers.Generic_Array_Sort 
    (Index_Type => Natural; 
    Element_Type => Ada.Strings.Unbounded.Unbounded_String, 
    Array_Type => String_Array 
); 

Ejemplo del uso:

using Ada.Strings.Unbounded; 

    Example : String_Array := (To_Unbounded_String ("Joe"), 
           To_Unbounded_String ("Jim"), 
           To_Unbounded_String ("Jane"), 
           To_Unbounded_String ("Fred"), 
           To_Unbounded_String ("Bertha"), 
           To_Unbounded_String ("Joesphus"), 
           To_Unbounded_String ("Jonesey")); 
begin 
    Sort (Example); 
    ... 
end; 

Answer 11

En C, esta solución maneja correctamente los números con ceros a la izquierda:

#include <stdlib.h> 
#include <ctype.h> 

/* like strcmp but compare sequences of digits numerically */ 
int strcmpbynum(const char *s1, const char *s2) { 
    for (;;) { 
    if (*s2 == '\0') 
     return *s1 != '\0'; 
    else if (*s1 == '\0') 
     return 1; 
    else if (!(isdigit(*s1) && isdigit(*s2))) { 
     if (*s1 != *s2) 
     return (int)*s1 - (int)*s2; 
     else 
     (++s1, ++s2); 
    } else { 
     char *lim1, *lim2; 
     unsigned long n1 = strtoul(s1, &lim1, 10); 
     unsigned long n2 = strtoul(s2, &lim2, 10); 
     if (n1 > n2) 
     return 1; 
     else if (n1 < n2) 
     return -1; 
     s1 = lim1; 
     s2 = lim2; 
    } 
    } 
} 

Si desea utilizarlo con qsort nosotros, e esta función auxiliar:

static int compare(const void *p1, const void *p2) { 
    const char * const *ps1 = p1; 
    const char * const *ps2 = p2; 
    return strcmpbynum(*ps1, *ps2); 
} 

Y se puede hacer algo en el orden de

char *lines = ...; 
qsort(lines, next, sizeof(lines[0]), compare); 

Answer 12

Python, utilizando itertools:

def natural_key(s): 
    return tuple(
     int(''.join(chars)) if isdigit else ''.join(chars) 
     for isdigit, chars in itertools.groupby(s, str.isdigit) 
    ) 

Resultado:

>>> natural_key('abc-123foo456.xyz') 
('abc-', 123, 'foo', 456, '.xyz') 

clasificación :

>>> sorted(['1.1.1', '1.10.4', '1.5.0', '42.1.0', '9', 'banana'], key=natural_key) 
['1.1.1', '1.5.0', '1.10.4', '9', '42.1.0', 'banana'] 

Answer 13

Mi implementación en Clojure 1.1:

(ns alphanumeric-sort 
    (:import [java.util.regex Pattern])) 

(defn comp-alpha-numerical 
    "Compare two strings alphanumerically." 
    [a b] 
    (let [regex (Pattern/compile "[\\d]+|[a-zA-Z]+") 
     sa (re-seq regex a) 
     sb (re-seq regex b)] 
    (loop [seqa sa seqb sb] 
     (let [counta (count seqa) 
      countb (count seqb)] 
     (if-not (not-any? zero? [counta countb]) (- counta countb) 
      (let [c (first seqa) 
       d (first seqb) 
       c1 (read-string c) 
       d1 (read-string d)] 
      (if (every? integer? [c1 d1]) 
       (def result (compare c1 d1)) (def result (compare c d))) 
      (if-not (= 0 result) result (recur (rest seqa) (rest seqb))))))))) 

(sort comp-alpha-numerical ["a1" "a003" "b2" "a10" "a2" "1" "10" "20" "2" "c100"]) 

Resultado:

("1" "2" "10" "20" "A1" "a2" "a003" "A10" "b2" "c100")

Answer 14

PHP tiene una función fácil "natsort" para hacer eso, y yo implementa por mí mismo:

<?php 
$temp_files = array('+====','-==',"temp15-txt","temp10.txt", 
"temp1.txt","tempe22.txt","temp2.txt"); 
$my_arr = $temp_files; 


natsort($temp_files); 
echo "Natural order: "; 
print_r($temp_files); 


echo "My Natural order: "; 
usort($my_arr,'my_nat_func'); 
print_r($my_arr); 


function is_alpha($a){ 
    return $a>='0'&&$a<='9' ; 
} 

function my_nat_func($a,$b){ 
    if(preg_match('/[0-9]/',$a)){ 
     if(preg_match('/[0-9]/',$b)){ 
      $i=0; 
      while(!is_alpha($a[$i])) ++$i; 
      $m = intval(substr($a,$i));    
      $i=0; 
      while(!is_alpha($b[$i])) ++$i; 
      $n = intval(substr($b,$i)); 
      return $m>$n?1:($m==$n?0:-1); 
     } 
     return 1; 
    }else{ 
     if(preg_match('/[0-9]/',$b)){ 
      return -1; 
     } 
     return $a>$b?1:($a==$b?0:-1); 
    } 
}