Pull to refresh

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

Reading time 14 min
Views 46K
Задача сортировки является едва ли не наиболее часто решаемой программистами проблемой. Несмотря на то, что распространённых алгоритмов не так много и все они давно написаны и оптимизированы для любых языков и платформ, в исходниках то и дело мелькают методы 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:
Hubs:
+28
Comments 16
Comments Comments 16

Articles