Сортировка строк
Проблема скрытой константы O(L)
Когда мы оцениваем сложность алгоритмов сортировки, мы обычно говорим про количество сравнений элементов. Например, сортировка слиянием делает O(N log N) сравнений, где N - количество элементов.
Но если элементами являются строки (или длинные массивы), само сравнение перестает быть мгновенным. Чтобы понять, что строка "алгоритм" меньше строки "алгоритмы", нам нужно посимвольно сравнить их. Если строки почти идентичны и различаются только в самом конце, сравнение потребует прохода по всем символам.
- Сложность сортировки слиянием для массива из N строк длины L:
O(N * log N * L).
Специфичные алгоритмы для строк
Вместо того чтобы сравнивать строки целиком (как монолитные объекты), гораздо эффективнее рассматривать их как последовательность символов. Существуют алгоритмы, которые вообще не используют прямое сравнение строк друг с другом:
1. Цифровая сортировка (Radix Sort) для строк
Мы можем сортировать строки посимвольно (как разряды в числах).
- LSD (Least Significant Digit) Radix Sort: Сортировка с конца (с правого символа). Хорошо работает, если все строки одинаковой длины.
- MSD (Most Significant Digit) Radix Sort: Сортировка с начала (с левого символа). Массив разбивается на "корзины" по первому символу, затем каждая корзина рекурсивно сортируется по второму символу и т.д. Это высокоэффективный метод для строк, так как он не проверяет лишние символы.
Алгоритм поразрядной сортировки работает следующим образом:
- Массив строк разбивается на корзины на основе первого символа.
- Внутри каждой непустой корзины алгоритм рекурсивно сортирует строки уже по второму символу, и так далее.
- После распределения результаты конкатенируются в итоговый отсортированный массив.
2. Префиксные деревья (Trie)
Можно вставить все строки в специальную структуру данных - префиксное дерево (Trie). Вставка N строк длины L займет время O(N * L). Затем мы просто обходим это дерево в глубину (DFS) и выписываем слова в алфавитном порядке. Это элегантное и быстрое решение, но оно потребляет очень много оперативной памяти для хранения узлов дерева.
3. Трехпутевая быстрая сортировка строк (3-Way Radix Quick Sort)
Это гибрид сортировки Хоара и MSD цифровой сортировки. Разработан Робертом Седжвиком. На каждом шаге выбирается один опорный символ (pivot), и массив строк разбивается на три части: те, где текущий символ меньше опорного, равен опорному и больше опорного. Алгоритм отлично справляется с массивами, где много строк с общими префиксами.
При сортировке строк используется лексикографический (алфавитный) порядок. Он опирается на коды символов в таблице кодировок (ASCII или Unicode). Из-за этого заглавные буквы обычно идут раньше строчных (код 'A' = 65, код 'a' = 97), а цифры раньше букв.
Коротко: главное
- Сравнение двух длинных строк не является мгновенным и в худшем случае занимает время O(L).
- Обычные алгоритмы (сортировка слиянием, сортировка Хоара) на массиве строк длины L работают за O(N * L * log N).
- Для эффективной сортировки строк используют алгоритмы, рассматривающие строки посимвольно.
- MSD/LSD Radix Sort, префиксные деревья (Trie) и трехпутевая быстрая сортировка строк позволяют избежать прямых сравнений слов целиком.
- При сортировке строк учитывается лексикографический порядок (коды символов в таблице кодировок).
Проверьте себя
Чему равна временная сложность классической сортировки слиянием для массива из N строк, каждая из которых имеет длину L?