ナチュラルソートアルゴリズム

Question

ストリングの配列を別のプログラミング言語で並べ替えるにはどうすればいいですか？naturallyあなたの実装とそれがどの言語であるかを回答に投稿してください。

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(""); 
} 

MySQLの

Source

Answer 2

、私が個人的にhhttpに利用可能であるDrupalのモジュールからのコードを使用します//drupalcode.org/project/natsort.git/blob /refs/heads/5.x-1.x:/natsort.install.mysql

基本的には、関数を作成するために、投稿SQLスクリプトを実行し、その後ORDER BY natsort_canon(field_name, 'natural')

0を使用しますここ

は、機能についてのreadmeです： http://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/README.txt

Answer 3

OPがidomaticソート式について質問されている場合は、必ずしもすべての言語が組み込ま自然発現を有するCのために、私は<stdlib.h>に行くとqsortを使用すると思います。次の行の何か：

/* non-functional mess deleted */ 

引数を字句順にソートする。残念なことに、このイディオムは、cの方法を使わなかった人たちのために解析するのはむしろ難しいです。適切downvoteによってchastened

---

、私は実際にリンク先の記事を読んで。 Mea culpa。

いずれのケースでも、テストした単一のケースを除いて、元のコードは機能しませんでした。くそー。プレーンなバニラcはこの機能を持っておらず、通常のライブラリにもありません。

以下のコードは、ナチュラルのリンクをコマンドライン引数としてソートしています。 警告欄は軽度にテストされているためです。

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

このアプローチは非常に力強いですが、単純であり、おそらく命令的な言語で複製することができます。

Answer 4

私はこれをexample codeを使って自然なソートを行います。コードには、ブーストライブラリが必要です。

Answer 5

私はちょうどStrCmpLogicalWを使用します。それは、エクスプローラが使用するのと同じAPIなので、ジェフが望んでいるものとまったく同じです。確かに、それは移植性がありません。 C++で

：

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

しかし、実際に私は何をこのようにソートする機会がなかった。

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

ここで質問がにリンクされているthe articleにthe codeのクリーンアップです。ここで

Answer 7

あなたは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() 

のUnicode文字列をサポートするために、.isdecimal()代わりに.isdigit()の使用すべきです。

.isdigit()また、一部のロケールではPython 2のbytestring（で受け付けられない戻り値）が失敗することがあります（例：'\xb2' ('²') in cp1252 locale on Windows）。

Answer 8

ただ、エリック・ノーマンにより、Common Lispではいくつかの素晴らしい作品へのリンク：Tclのために

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

Answer 9

、lsortする-dict（辞書）オプション：

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

Answer 10

注ことそのような質問の多くは、Rosetta Code Wikiにご相談ください。私は整数の並べ替えの項目から私の答えを適応させた。

このようなことをするシステムのプログラミング言語では、一般的には特殊化された文字列処理言語よりも醜いでしょう。幸いにもAdaの場合、最新のバージョンにはこの種のタスクのためのライブラリルーチンがあります。

私はあなたが次の行（警告、コンパイルされていない！）に沿って何か行うことができます信じていエイダ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 
); 

使用例：Cで

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

を、このソリューションが正しく数値を扱います先行ゼロ付き：

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

qsortと一緒に使用する場合は、 Eこの補助機能：

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

そして、あなたは

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

Answer 12

の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 13

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"]) 

結果：

（ "1" "2" "10" "20" "A1"、 "A2"、 "A003" "A10" "B2" "C100"）

Answer 14

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