Алгоритм естественной сортировки

Question

Как вы сортируете массив строк естественно в разных языках программирования? Опубликуйте свою реализацию и на каком языке она написана в ответе.

Answer 1

Python, используя itertools:

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

Результат:

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

Сортировка:

>>> 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 2

Обратите внимание, что по большинству таких вопросов вы можете просто обратиться к Rosetta Code Wiki . Я адаптировал свой ответ из записи для сортировки целых чисел.

На языке программирования системы делать что-то подобное, как правило, будет сложнее, чем с помощью специализированного языка обработки строк. К счастью для Ады, в самой последней версии есть подпрограмма библиотеки именно для такого рода задач.

Для Ады 2005 я думаю, что вы могли бы сделать что-то вроде следующего (предупреждение, не скомпилировано!):

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

Пример использования:

    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 3

php имеет простую функцию "natsort", чтобы сделать это, и я сам ее реализую:

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

Answer 4

Для Tcl опция -dict (словарь) для lsort:

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