Задача сортировки является едва ли не наиболее часто решаемой программистами проблемой. Несмотря на то, что распространённых алгоритмов не так много и все они давно написаны и оптимизированы для любых языков и платформ, в исходниках то и дело мелькают методы SortList() и им подобные. Наверное, каждый из нас не раз писал сортировку пузырьком и удивлялся, почему же она не работает с первого раза.
Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).
Под катом —велосипед подробный алгоритм на JavaScript. На оптимальность и красоту он не претендует, но всё же лучше, чем многопроходная реализация «в лоб».
Сам алгоритм сортировки мы писать не будем, а воспользуемся встроенным методом Array.sort(). Поэтому «главная функция» будет выглядеть как-то так:
Осталось написать функцию compareStrings() для сравнения строк. Это можно сделать по-разному, но мне пришёл в голову следующий подход: отделим числа от текста в составе строк, а затем пройдём по полученным массивам до первого различия между строками (или числами) с одинаковыми индексами. Разделять строки будет функция splitString() (о ней чуть позже), а само сравнение будет иметь примерно следующий вид:
Однако с этим подходом не всё так гладко: большинство строк, которые приходится сравнивать, различаются начиная с первых символов, то есть splitString() делает много лишней работы. Но это поправимо с помощью отложенных вычислений — пусть splitString() возвращает не готовый массив, а объект-итератор с методами next() и count(). Благодаря замыканиям в JavaScript реализация получилась не слишком объёмной:
(UPD в конце поста)
Напишем вспомогательные функции — xor() и isDigit():
Теперь вернёмся к функции сравнения строк compareStrings(). С введениeм итераторов общая логика почти не изменилась:
(UPD в конце поста)
Наконец, напишем функцию сортировки, соберём всё воедино и «причешем» код:
(UPD в конце поста)
Буду благодарен за найденные баги, советы и предложения по коду. Надеюсь, кому-то было интересно, а может быть даже полезно.
UPD:
В комментариях Alex_At_Net заметил, что неплохо бы кешировать результаты разбиения строк, а standy предложил сразу разбить строки на части и сортировать уже готовые наборы фрагментов. В результате появилась исправленная и дополненная версия скрипта. В функцию сортировки добавлен необязательный параметр extractor — функция преобразования произвольного объекта в строку: теперь можно сортировать массивы любых объектов. Входной массив сразу преобразуется в массив сплиттеров, но само разбиение происходит только при обращении к фрагменту по индексу, только до нужного места и только один раз. Вместо метода next() у сплиттера теперь есть метод part(i), возвращающий фрагмент по индексу. Код ещё немного «причёсан» и «объектизирован». Выглядит это всё так:
C комментариями
Без комментариев
P.S.:
Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).
Под катом —
Сам алгоритм сортировки мы писать не будем, а воспользуемся встроенным методом 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.