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

    Задача сортировки является едва ли не наиболее часто решаемой программистами проблемой. Несмотря на то, что распространённых алгоритмов не так много и все они давно написаны и оптимизированы для любых языков и платформ, в исходниках то и дело мелькают методы SortList() и им подобные. Наверное, каждый из нас не раз писал сортировку пузырьком и удивлялся, почему же она не работает с первого раза.

    Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).

    Под катом — велосипед подробный алгоритм на JavaScript. На оптимальность и красоту он не претендует, но всё же лучше, чем многопроходная реализация «в лоб».



    Сам алгоритм сортировки мы писать не будем, а воспользуемся встроенным методом Array.sort(). Поэтому «главная функция» будет выглядеть как-то так:
    function naturalSort(stringArray) {
      var arr = stringArray;
      // ...
      return arr.sort(compareStrings) // функция сравнения ещё не написана
    }

    Осталось написать функцию compareStrings() для сравнения строк. Это можно сделать по-разному, но мне пришёл в голову следующий подход: отделим числа от текста в составе строк, а затем пройдём по полученным массивам до первого различия между строками (или числами) с одинаковыми индексами. Разделять строки будет функция splitString() (о ней чуть позже), а само сравнение будет иметь примерно следующий вид:
    function compareStrings(str1, str2) {
      // обычное сравнение строк или чисел
      var compare = function(a, b) {  
        return (a < b) ? -1 : (a > b) ? 1 : 0;
      };
      // разделяем строки; splitString() напишем позже
      var parts1 = splitString(str1);
      var parts2 = splitString(str2);
      // перебираем части до минимальной длины
      var minLength = Math.min(parts1.length, parts2.length); 
      for (var i = 0; i < minLength; i++) {
        // здесь будем сравнивать части с одинаковыми индексами
      }
      // если в одной из строк частей больше и при этом
       // все, кроме "лишних", совпадают с другой строкой, то эта строка "больше"
      return compare(parts1.length, parts2.length); 
    }

    Однако с этим подходом не всё так гладко: большинство строк, которые приходится сравнивать, различаются начиная с первых символов, то есть splitString() делает много лишней работы. Но это поправимо с помощью отложенных вычислений — пусть splitString() возвращает не готовый массив, а объект-итератор с методами next() и count(). Благодаря замыканиям в JavaScript реализация получилась не слишком объёмной:
    (UPD в конце поста)
    function splitString(str) {
      var from = 0;              // начальный индекс для slice()
      var index = 0;             // индекс для прохода по строке
      var count = 0;             // количество уже найденных частей    
      var splitter = {};         // будущий итератор
      // аналог свойства только для чтения   с помощью замыкания  
      splitter.count = function () {
        return count;
      }
      // возвращает следующую часть строки  
      splitter.next = function() {
        // если строка закончилось - вернём null
        if (index === str.length) {
          return null;
        }
        // перебираем символы до границы между нецифровыми символами и цифрами
        while(++index) {
          var currentIsDigit = isDigit(str.charAt(index - 1));  // isDigit() ещё не написана
          var nextChar = str.charAt(index);
          var currentIsLast = (index === str.length);
          // граница - если символ последний,
           // или если текущий и следующий символы разнотипные (цифра / не цифра)
        var isBorder = currentIsLast ||
            xor(currentIsDigit, isDigit(nextChar));             // xor() тоже напишем потом
        if (isBorder) {
          var part = str.slice(from, index);
            from = index;
            count++;
            return {
              IsNumber: currentIsDigit,
              Value: currentIsDigit ? Number(part) : part
            };
        } // end if
        } // end while
      }; // end next()
        
      return splitter;
    }

    Напишем вспомогательные функции — xor() и isDigit():
    function xor(a, b) {
      return a ? !b : b;
    }

    function isDigit(chr) {
      var charCode = function(ch) {
        return ch.charCodeAt(0);
      };
      var code = charCode(chr);
      return (code >= charCode('0')) && (code <= charCode('9'));
    }

    Теперь вернёмся к функции сравнения строк compareStrings(). С введениeм итераторов общая логика почти не изменилась:
    (UPD в конце поста)
    function compareStrings(str1, str2) {
      // обычное сравнение строк или чисел
      var compare = function(a, b) {  
          return (a < b) ? -1 : (a > b) ? 1 : 0;
      };
      // получаем итераторы для строк
      var splitter1 = splitString(str1);
      var splitter2 = splitString(str2);
      // перебираем части
      while (true) {
        var first = splitter1.next();
        var second = splitter2.next();
        // если обе части существуют ...
        if (null !== first && null !== second) {
          // части разных типов (цифры либо нецифровые символы)  
          if (xor(first.IsNumber, second.IsNumber)) {
            // цифры всегда "меньше"      
            return first.IsNumber ? -1 : 1;        
          // части одного типа можно просто сравнить
          } else {                    
            var comp = compare(first.Value, second.Value);    
            if (comp != 0) {
              return comp;
            }
          } // end if
        // ... если же одна из строк закончилась - то она "меньше"
        } else {
          return compare(splitter1.count(), splitter2.count());
        }
      } // end while
    }

    Наконец, напишем функцию сортировки, соберём всё воедино и «причешем» код:
    (UPD в конце поста)
    function naturalSort(stringArray) {
      // логическое исключающее "или"
      var xor = function(a, b) {
        return a ? !b : b;
      };
      // проверяет, является ли символ цифрой
      var isDigit = function(chr) {
        var charCode = function(ch) {
          return ch.charCodeAt(0);
        };
        var code = charCode(chr);
        return (code >= charCode('0')) && (code <= charCode('9'));
      };
      // возвращает итератор для строки
      var splitString = function(str) {
        var from = 0;            // начальный индекс для slice()
        var index = 0;            // индекс для прохода по строке
        var count = 0;            // количество уже найденных частей    
        var splitter = {};          // будущий итератор
        // аналог свойства только для чтения  
        splitter.count = function () {
          return count;
        }
        // возвращает следующую часть строки  
        splitter.next = function() {
          // если строка закончилось - вернём null
          if (index === str.length) {
            return null;
          }
          // перебираем символы до границы между нецифровыми символами и цифрами
          while(++index) {
            var currentIsDigit = isDigit(str.charAt(index - 1));  
            var nextChar = str.charAt(index);
            var currentIsLast = (index === str.length);
            // граница - если символ последний,
             // или если текущий и следующий символы разнотипные (цифра / не цифра)
            var isBorder = currentIsLast ||
              xor(currentIsDigit, isDigit(nextChar));        
            if (isBorder) {
              var part = str.slice(from, index);
              from = index;
              count++;
              return {
                IsNumber: currentIsDigit,
                Value: currentIsDigit ? Number(part) : part
              };
            } // end if
          } // end while
        }; // end next()  
        return splitter;
      };
      // сравнивает строки в "естественном" порядке
      var compareStrings = function(str1, str2) {
        // обычное сравнение строк или чисел
        var compare = function(a, b) {  
            return (a < b) ? -1 : (a > b) ? 1 : 0;
        };
        // получаем итераторы для строк
        var splitter1 = splitString(str1);
        var splitter2 = splitString(str2);
        // перебираем части
        while (true) {
          var first = splitter1.next();
          var second = splitter2.next();
          // если обе части существуют ...
          if (null !== first && null !== second) {
            // части разных типов (цифры либо нецифровые символы)  
            if (xor(first.IsNumber, second.IsNumber)) {
              // цифры всегда "меньше"      
              return first.IsNumber ? -1 : 1;        
            // части одного типа можно просто сравнить
            } else {                    
              var comp = compare(first.Value, second.Value);    
              if (comp != 0) {
                return comp;
              }
            } // end if
          // ... если же одна из строк закончилась - то она "меньше"
          } else {
            return compare(splitter1.count(), splitter2.count());
          }
        } // end while
      }
      // собственно сортировка
      var arr = stringArray;
      return arr.sort(compareStrings);  
    }


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

    UPD:
    В комментариях Alex_At_Net заметил, что неплохо бы кешировать результаты разбиения строк, а standy предложил сразу разбить строки на части и сортировать уже готовые наборы фрагментов. В результате появилась исправленная и дополненная версия скрипта. В функцию сортировки добавлен необязательный параметр extractor — функция преобразования произвольного объекта в строку: теперь можно сортировать массивы любых объектов. Входной массив сразу преобразуется в массив сплиттеров, но само разбиение происходит только при обращении к фрагменту по индексу, только до нужного места и только один раз. Вместо метода next() у сплиттера теперь есть метод part(i), возвращающий фрагмент по индексу. Код ещё немного «причёсан» и «объектизирован». Выглядит это всё так:

    function naturalSort(array, extractor) {
      "use strict";
      // преобразуем исходный массив в массив сплиттеров
      var splitters = array.map(makeSplitter);
      // сортируем сплиттеры
      var sorted = splitters.sort(compareSplitters);
      // возвращаем исходные данные в новом порядке
      return sorted.map(function (splitter) {
        return splitter.item;
      });
      // обёртка конструктора сплиттера
      function makeSplitter(item) {
        return new Splitter(item);
      }
      // конструктор сплиттера
      //    сплиттер разделяет строку на фрагменты "ленивым" способом
      function Splitter(item) {
        var index = 0;           // индекс для прохода по строке  
        var from = 0;           // начальный индекс для фрагмента
        var parts = [];         // массив фрагментов
        var completed = false;       // разобрана ли строка полностью
        // исходный объект
        this.item = item;
        // ключ - строка
        var key = (typeof (extractor) === 'function') ?
          extractor(item) :
          item;
        this.key = key;
        // количество найденных фрагментов
        this.count = function () {
          return parts.length;
        };
        // фрагмент по индексу (по возможности из parts[])
        this.part = function (i) {
          while (parts.length <= i && !completed) {
            next();   // разбираем строку дальше
          }
          return (i < parts.length) ? parts[i] : null;
        };
        // разбор строки до следующего фрагмента
        function next() {
          // строка ещё не закончилась
          if (index < key.length) {
            // перебираем символы до границы между нецифровыми символами и цифрами
            while (++index) {
              var currentIsDigit = isDigit(key.charAt(index - 1));
              var nextChar = key.charAt(index);
              var currentIsLast = (index === key.length);
              // граница - если символ последний,
              // или если текущий и следующий символы разнотипные (цифра / не цифра)
              var isBorder = currentIsLast ||
                xor(currentIsDigit, isDigit(nextChar));
              if (isBorder) {
                // формируем фрагмент и добавляем его в parts[]
                var partStr = key.slice(from, index);
                parts.push(new Part(partStr, currentIsDigit));
                from = index;
                break;
              } // end if
            } // end while
            // строка уже закончилась
          } else {
            completed = true;
          } // end if
        } // end next
        // конструктор фрагмента
        function Part(text, isNumber) {
          this.isNumber = isNumber;
          this.value = isNumber ? Number(text) : text;
        }
      }
      // сравнение сплиттеров
      function compareSplitters(sp1, sp2) {
        var i = 0;
        do {
          var first = sp1.part(i);
          var second = sp2.part(i);
          // если обе части существуют ...
          if (null !== first && null !== second) {
            // части разных типов (цифры либо нецифровые символы)  
            if (xor(first.isNumber, second.isNumber)) {
              // цифры всегда "меньше"      
              return first.isNumber ? -1 : 1;
              // части одного типа можно просто сравнить
            } else {
              var comp = compare(first.value, second.value);
              if (comp != 0) {
                return comp;
              }
            } // end if
            // ... если же одна из строк закончилась - то она "меньше"
          } else {
            return compare(sp1.count(), sp2.count());
          }
        } while (++i);
        // обычное сравнение строк или чисел
        function compare(a, b) {
          return (a < b) ? -1 : (a > b) ? 1 : 0;
        };
      };
      // логическое исключающее "или"
      function xor(a, b) {
        return a ? !b : b;
      };
      // проверка: является ли символ цифрой
      function isDigit(chr) {
        var code = charCode(chr);
        return (code >= charCode('0')) && (code <= charCode('9'));
        function charCode(ch) {
          return ch.charCodeAt(0);
        };
      };
    }


    C комментариями
    Без комментариев

    P.S.:
    function thanks() {
      alert('Cпасибо PoiSoN за Source Code Highlighter');
    };


    * This source code was highlighted with Source Code Highlighter.
    Share post

    Comments 16

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

      И такой вопрос: а сколько раз выполняется парсер для каждой строки из массива? Может имеет смысл кешировать разобранные фрагменты?
        0
        Скорее, имеет смысл кешировать сразу результаты сравнение, чтобы заново не сравнивать фрагменты.
          0
          Стоп, а сравнения-то по одному разу максимум для каждой пары выполняются! Сглупил, пора спать)
          0
          Обновил, в кешировании теперь нет необходимости :)
          +3
          После первых двух абзацев решил себя проверить, написал функцию сравнения:
          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'] ), и затем сравниваем каждый элемент получившихся массивов как строки и числа соотв.
            0
            Ага, первая версия splitString() работала у меня на том же регэспе)
              +2
              К чему тогда было усложнять :)
              Дабы как-то оптимизировать можно прогнать регексп по массиву всего один раз перед сортировкой:
              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' ] ) )
              
              
                0
                У меня оптимизация пошла совсем в другом направлении :) А ваш код, действительно, выглядит всяко понятнее.
              0
              … поправка, вместо return 0;
              return str1split.length - str2split.length; //если у одной из строк остался хвост, значит она больше

              С первого раза без багов никогда не получается.
              +1
              Еще один велосипед, этот 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.
                –2
                Код сортирует так:

                cote
                coté
                côte
                côté

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

                cote
                côte
                coté
                côté
                  –1
                  Хотя нет, вроде бы кусочки строк сравниваются родной функцией ЯваСкрипта? Тогда должно работать как надо.
                  0
                  Если бы мне срочно потребовался натуральный поиск, я бы сделал что то вроде. Жаль, что такое решение не сработает на строках типа '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+/, '')
                  })
                  
                  

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

                    p.p.s. чем то ваш вариант с кешированием похож на мой
                      –1
                      Вот реализация на питоне. Я думаю, что на джаваскрипте можно сделать нечто подобное тоже.

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

                        Only users with full accounts can post comments. Log in, please.