Алгоритмы сортировки с учетом локали

Сортировка строк в JavaScript при работе с разными языками требует учёта правил конкретной локали, поскольку лексикографический порядок символов не совпадает с привычным «байтовым» или Unicode-кодовым сравнением. Базовый механизм сортировки, использующий оператор сравнения < и >, опирается на кодовые точки UTF-16 и не учитывает особенности языка: диакритические знаки, регистры, составные символы и национальные алфавиты.

Стандартная сортировка массивов через Array.prototype.sort() без компаратора использует преобразование элементов в строки и сравнение их по Unicode-кодам.

["z", "a", "ä", "b"].sort();

Результат зависит от кодировки символов и не отражает языковую корректность. Например, символ ä может оказаться после z, хотя в немецкой локали он должен рассматриваться как вариант a.

Основные ограничения такого подхода:

  • отсутствие учёта локали
  • некорректная обработка диакритики
  • игнорирование правил регистра
  • отсутствие поддержки числовой сортировки строковых чисел
  • различия в трактовке составных символов

Эти проблемы устраняются через механизмы Intl.

Intl.Collator как основа локализованной сортировки

Intl.Collator предоставляет объект, реализующий сравнение строк с учётом языковых правил. Он используется как компаратор в Array.prototype.sort().

Базовая конструкция:

const collator = new Intl.Collator("ru");
collator.compare("а", "б");

Возвращаемые значения:

  • отрицательное число — первая строка меньше второй
  • ноль — строки эквивалентны
  • положительное число — первая строка больше второй

Использование в сортировке:

const collator = new Intl.Collator("ru");

["яблоко", "арбуз", "груша"].sort(collator.compare);

Локали и их влияние на порядок сортировки

Локаль определяет правила сравнения символов. Например:

  • "en" — английские правила
  • "de" — немецкие правила (умлауты и расширенные символы)
  • "tr" — турецкая локаль с особой обработкой i/İ
  • "ru" — кириллица с собственным алфавитным порядком

Пример:

const en = new Intl.Collator("en");
const de = new Intl.Collator("de");

["a", "ä", "z"].sort(en.compare);
["a", "ä", "z"].sort(de.compare);

Результаты могут различаться из-за разных трактовок ä.

Параметры Intl.Collator

sensitivity

Определяет уровень различий между строками.

new Intl.Collator("en", { sensitivity: "base" });

Варианты:

  • "base" — игнорируются диакритика и регистр
  • "accent" — учитываются диакритические знаки
  • "case" — учитывается регистр
  • "variant" — полное различие символов

Пример поведения:

const collator = new Intl.Collator("en", { sensitivity: "base" });

collator.compare("a", "A"); // 0
collator.compare("a", "á"); // 0

numeric

Позволяет корректно сортировать числа внутри строк.

new Intl.Collator("en", { numeric: true });

Без этого параметра сортировка будет лексикографической:

["2", "10", "1"].sort(); 
// ["1", "10", "2"]

С включённой числовой логикой:

const collator = new Intl.Collator("en", { numeric: true });

["2", "10", "1"].sort(collator.compare);
// ["1", "2", "10"]

caseFirst

Определяет приоритет регистра:

  • "upper" — заглавные первыми
  • "lower" — строчные первыми
  • "false" — без приоритета
new Intl.Collator("en", { caseFirst: "upper" });

Алгоритмическая основа сортировки с Intl.Collator

Метод sort() в JavaScript обычно использует адаптацию алгоритма с временной сложностью O(n log n). Конкретная реализация зависит от движка (V8, SpiderMonkey, JavaScriptCore), но принцип остаётся единым: сортировка строится на основе функции сравнения.

При использовании Intl.Collator сравнение строк делегируется ICU (International Components for Unicode), что означает:

  • предварительную нормализацию строк
  • применение правил локали
  • построение колляционных ключей

Колляционные ключи и оптимизация

Intl.Collator может внутренне создавать «ключи сортировки» (sort keys), чтобы ускорить многократные сравнения.

Без кэширования:

["яблоко", "арбуз", "груша"].sort(
  (a, b) => new Intl.Collator("ru").compare(a, b)
);

Этот подход неэффективен, поскольку создаётся новый Collator для каждого сравнения.

Оптимизированный вариант:

const collator = new Intl.Collator("ru");

["яблоко", "арбуз", "груша"].sort(collator.compare);

Unicode-нормализация и её влияние

Строки могут иметь разные Unicode-представления одного и того же символа. Например:

  • составной символ é
  • комбинация e + ́

Intl.Collator учитывает нормализацию, обеспечивая эквивалентность таких форм.

const collator = new Intl.Collator("fr");

collator.compare("é", "e\u0301");

Результат трактуется как равенство при соответствующей чувствительности.

Роль sensitivity в Unicode-сравнении

Четыре уровня чувствительности определяют глубину сравнения:

  • base — базовый символ
  • accent — диакритика
  • case — регистр
  • variant — полная спецификация

Пример различий:

const base = new Intl.Collator("en", { sensitivity: "base" });
const variant = new Intl.Collator("en", { sensitivity: "variant" });

base.compare("resume", "résumé");     // 0
variant.compare("resume", "résumé");  // различны

Локально-зависимые особенности сортировки

Некоторые языки имеют нестандартные правила:

  • Турецкий язык различает i, İ, ı, I
  • Немецкий язык может трактовать ß как ss
  • Шведский алфавит помещает å, ä, ö в конец
  • Французский учитывает апострофы и дефисы при вторичных сравнениях

Эти правила полностью инкапсулируются в ICU и не требуют ручной обработки.

Производительность и повторное использование Collator

Создание Intl.Collator является относительно дорогой операцией из-за загрузки правил локали и подготовки внутренних таблиц сравнения. Поэтому эффективная стратегия заключается в переиспользовании одного экземпляра:

const collator = new Intl.Collator("ru", {
  sensitivity: "base",
  numeric: true
});

function sortNames(list) {
  return list.sort(collator.compare);
}

Такой подход снижает накладные расходы при массовых операциях сортировки.

Сравнение localeCompare и Intl.Collator

Альтернативой является метод String.prototype.localeCompare:

"a".localeCompare("b", "ru");

Он поддерживает параметры локали, но при массовых операциях менее эффективен, чем предварительно созданный Intl.Collator.

Сравнение подходов:

  • localeCompare — удобен для единичных сравнений
  • Intl.Collator — оптимизирован для повторного использования

Стабильность сортировки и колляция

Современные движки JavaScript обеспечивают стабильную сортировку, что означает сохранение относительного порядка равных элементов.

При использовании Intl.Collator стабильность сохраняется, но итоговый порядок зависит от:

  • локали
  • sensitivity
  • наличия числовой сортировки

Комбинирование ключей сортировки

В сложных структурах данных часто требуется многоуровневая сортировка:

const collator = new Intl.Collator("ru", { numeric: true });

users.sort((a, b) =>
  collator.compare(a.lastName, b.lastName) ||
  collator.compare(a.firstName, b.firstName)
);

Такой подход реализует цепочку критериев сравнения, где следующий уровень используется только при равенстве предыдущего.

Влияние нормализации данных перед сортировкой

Перед использованием Intl.Collator часто выполняется подготовка данных:

  • приведение к единому регистру (при необходимости)
  • удаление лишних пробелов
  • нормализация Unicode (NFC/NFD)
function normalize(str) {
  return str.normalize("NFC");
}

Это уменьшает неоднозначности при сравнении строк из разных источников.

Алгоритмическая модель сравнения

С точки зрения алгоритмов, процесс сортировки с локалью включает:

  • преобразование строки в колляционный ключ
  • сравнение ключей вместо сырых строк
  • использование стандартного алгоритма сортировки массива (quicksort/timsort в зависимости от движка)

Таким образом, сложность операции определяется как:

  • O(n log n) сравнений
  • каждая операция сравнения — зависимость от длины строки и локальных правил ICU

Практическая модель применения

Сортировка с учётом локали применяется в:

  • поисковых системах
  • интерфейсах каталогов
  • CRM и ERP системах
  • мультиязычных пользовательских интерфейсах
  • обработке имен, адресов, товаров

Во всех этих случаях корректность сортировки важнее чистой производительности, поскольку влияет на восприятие структуры данных пользователем.

Оглавление