Pull to refresh

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

Algorithms *
Задача сортировки является едва ли не наиболее часто решаемой программистами проблемой. Несмотря на то, что распространённых алгоритмов не так много и все они давно написаны и оптимизированы для любых языков и платформ, в исходниках то и дело мелькают методы 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.
Tags: сортировкаjavascriptалгоритмыестественная сортировкаnatural sort
Hubs: Algorithms
Total votes 38: ↑33 and ↓5 +28
Comments 16
Comments Comments 16

Popular right now