Естественная сортировка строк на JavaScript

[Alex_At_Net]

Вообще compareStrings функция имеет смысл и отдельно использовать — когда хочется использовать объектный, а не процедурный синтаксис.

И такой вопрос: а сколько раз выполняется парсер для каждой строки из массива? Может имеет смысл кешировать разобранные фрагменты?

[ZIJ]

Скорее, имеет смысл кешировать сразу результаты сравнение, чтобы заново не сравнивать фрагменты.

[ZIJ]

Стоп, а сравнения-то по одному разу максимум для каждой пары выполняются! Сглупил, пора спать)

[ZIJ]

Обновил, в кешировании теперь нет необходимости :)

[standy]

После первых двух абзацев решил себя проверить, написал функцию сравнения:

function compareStrings(str1, str2) {
	var rx = /([^\d]+|\d+)/ig;
	var str1split = str1.match( rx );
	var str2split = str2.match( rx );
	for(var i=0, l=Math.min(str1split.length, str2split.length); i < l; i++) {
		var s1 = str1split[i], 
		    s2 = str2split[i];
		if (s1 === s2) continue;
		if (isNaN(+s1) || isNaN(+s2))
			return s1 > s2 ? 1 : -1;
		else
			return +s1 - s2;		
	}
	return 0;
}
console.log( [ 'file2', 'file10', 'file1' ].sort(compareStrings) );

На оптимальность так же не претендует. Подход простой, разбиваем строку на массив — строки одтельно числа отдельно ( 't123est' ~> ['t', '123', 'est'] ), и затем сравниваем каждый элемент получившихся массивов как строки и числа соотв.

[ZIJ]

Ага, первая версия splitString() работала у меня на том же регэспе)

[standy]

К чему тогда было усложнять :)
Дабы как-то оптимизировать можно прогнать регексп по массиву всего один раз перед сортировкой:

function naturalSort(stringArray) {
	function compareStrings(str1, str2) {
		var str1split = arrSplitted[str1];
		var str2split = arrSplitted[str2];
		//for(.. итд
	}
	var arrSplitted = {};
	for (var i=0, l=stringArray.length; i<l; i++ ) {
		arrSplitted[stringArray[i]] = stringArray[i].match( /([^\d]+|\d+)/ig )
	}
	return stringArray.sort(compareStrings);	
}

console.log( naturalSort( [ 'file1', 'file10', 'file2' ] ) )

[ZIJ]

У меня оптимизация пошла совсем в другом направлении :) А ваш код, действительно, выглядит всяко понятнее.

[standy]

… поправка, вместо return 0;

return str1split.length - str2split.length; //если у одной из строк остался хвост, значит она больше

С первого раза без багов никогда не получается.

[nullbie]

Еще один велосипед, этот C-style :)

1. function isDigit(ch) {
2.   var code = ch.charCodeAt(0);
3.   return code >= '0'.charCodeAt(0) && code <= '9'.charCodeAt(0);
4. }
5.  
6. function readDigits(s, i0) {
7.   var result = 0;
8.   for (var i = i0; i < s.length; i++) {
9.     var digit = s.charCodeAt(i) - '0'.charCodeAt(0);
10.     if (digit < 0 || digit > 9) break;
11.     result = result * 10 + digit;
12.   }
13.   return { number: result, position: i };
14. }
15.  
16. function strnatcmp(s1, s2) {
17.   var i1 = 0;
18.   var i2 = 0;
19.   while (true) {
20.     if (i1 >= s1.length) return i2 >= s2.length ? 0 : -1;
21.     if (i2 >= s2.length) return 1;
22.  
23.     var ch1 = s1.charAt(i1);
24.     var ch2 = s2.charAt(i2);
25.  
26.     if (isDigit(ch1)) {
27.       if (!isDigit(ch2)) return -1;
28.  
29.       var n1 = readDigits(s1, i1);
30.       var n2 = readDigits(s2, i2);
31.  
32.       if (n1.number < n2.number) return -1;
33.       if (n1.number > n2.number) return 1;
34.  
35.       i1 = n1.position;
36.       i2 = n2.position;
37.       continue;
38.     }
39.     
40.     if (isDigit(ch2)) return 1;
41.     if (ch1 < ch2) return -1;
42.     if (ch1 > ch2) return 1;
43.  
44.     i1++;
45.     i2++;
46.   }
47. }

* This source code was highlighted with Source Code Highlighter.

[olpa]

Код сортирует так:

cote
coté
côte
côté

А по правилам французского языка должно быть:

cote
côte
coté
côté

[olpa]

Хотя нет, вроде бы кусочки строк сравниваются родной функцией ЯваСкрипта? Тогда должно работать как надо.

[AHDPEu]

Если бы мне срочно потребовался натуральный поиск, я бы сделал что то вроде. Жаль, что такое решение не сработает на строках типа 'word444port';

var test_arr = ['file10', 'file222', 'file2', 'file1', 'file'];

test_arr.sort(function(a, b){
    return a.replace(/\d+/, '') >= b.replace(/\d+/, '') && +a.replace(/\D+/, '') >= +b.replace(/\D+/, '')
})

[rPman]

Когда то я решил эту задачу тем, что сначала создал копию каждой строки, заменив числа в ней на числа фиксированной длинны (благо для строк где цифр было слишком много натуральная сортировка была не критична), т.е. 'sd4zx92' -> 'sd0004zx0092', а потом сортировал полученный массив штатным способом (на самом деле сортировал массив индексов, чтобы в результате все таки получить старые строки).

p.p.s. чем то ваш вариант с кешированием похож на мой

[ingspree]

Вот реализация на питоне. Я думаю, что на джаваскрипте можно сделать нечто подобное тоже.

def humankey(fn):
  '''Turn a string into a list of substrings and numbers.

  This can be used as a key function for ``sorted``::

    >>> s = lambda *x: list(sorted(x, key=humankey))
    >>> print s('up-1', 'up-5', 'up-15', 'up-50')
    ['up-1', 'up-5', 'up-15', 'up-50']
    >>> print s('up-1.sql', 'up.sql', 'up1.sql')
    ['up.sql', 'up1.sql', 'up-1.sql']
    >>> print s('up.rb', 'up.py') # check extension sorting
    ['up.py', 'up.rb']
  '''
  fn, ext = os.path.splitext(fn)
  return [int(s) if s.isdigit() else s for s in NUM_RE.split(fn)], ext


def humansort(l):
    return list(sorted(l, key=humankey))

[aaafwd]

FYI, реализация этой штуки в WebKit (Web Inspector): WebCore/inspector/front-end/ObjectPropertiesSection.js