Сортировка строк по словам

Сортировка слов является более полезной, нежели по символам. Однако типичные задачи требуют более быстрой методики сортировки, нежели описанные в главе 4. Здесь будет описываться

Существуют довольно мало причин, когда может потребоваться сортировка по символам. Гораздо больше причин для сортировки слов. Например, алфавитный указатель в книге – это список слов, найденных в книге с номерами страниц, на которых они встречаются. Слова в таком указателе должны быть отсортированы в алфавитном порядке. Однако даже создание такого списка – нелегкая работа, в котором сортировка играет ключевую роль.

Рассмотрим 400-страничную книгу с 500 словами на странице – книгу из 200 000 слов. Предположим, что в ней есть 3 000 уникальных слов. Каким образом они могут быть найдены? Самым простым способом было бы отсортировать всю книгу целиком, а затем пройтись по отсортированным строкам, выкинуть дубликаты, которые будут собраны вместе после сортировки. На самом деле, это не такая уж элементарная задача.

SelectSort требует n² операций чтения-записи файла длиной n символов. Предположим, что длина слова, в среднем, 5 символов, а также пробел между каждой парой слов. SelectSort потребует 200000* 200000=4*10¹⁰ операций чтения-записи слов и 24*10¹⁰ операций чтения-записи символов. Поскольку в году всего лишь 313 360 секунд в году, даже при миллионе операций чтения / записи в секунду эта задача потребует 9 месяцев выполнения, что на практике вовсе не подходит.

Другим способом создания списка слов, могло бы быть сортировка слов на первой странице, удаление дубликатов, затем на второй и т.д. На первой странице будет меньше 500 слов, но большинство из 3000 уникальных слов могут появиться на нескольких первых страницах. Как только это произойдет, на каждой странице необходимо будет отсортировать 3500 слов. В самом худшем случае нам придется сортировать 400 раз по 3500 слов. Количество операций чтения / записи на каждой странице будет равно 3500 * 3500 = 1.225 * 10⁷, а для всей книги – 3500 * 3500 * 400 = 4.9 * 10⁹ или 2.94 * 10¹⁰ операций чтения-записи символов. Что ж, раз в 8 лучше, однако все равно потребует больше месяца выполнения.

Стратегия сортировки, которую мы разработаем в дальнейшем, требует только n * k операций чтения для сортировки файла длиной n символов, где k – наименьшее целое, такое, что

2^k >= n

Для n = 200 000, количества слов в книге, количество операций чтения требуемое при такой сортировке будет:

n * k = 200000 * 18 = 3 600 000 (поскольку 2¹⁸ = 262144 > 200000)/

Опять таки, предположив, что слова у нас в среднем имеют длину 5 символов и должны быть разделены пробелом, сортировка слов потребует 21 600 000 операций считывания символов (немногим больше 21 секунды). Для простоты и сравнения с SelectSort эта новая стратегия сортировки будет разработана для сортировки символов.

10.2.1 Сортировка при помощи разделения и слияния.

Две отсортированные строки могут быть объединены в одну отсортированную строку при помощи циклического сравнивания их первых символов и перемещения символа, который должен быть первым в конец новой строки.

Например, рассмотрим две отсортированные строки:

Cow

Art

Сначала сравниваются a и c, и a выбирается в качестве начала новой строки, сравнивая c и r, мы добавляем символ c в конец строки. Выполнение пошагового слияния строк показано в следующей таблице:

Таким образом, если файл может быть разделен на отсортированные части, называемые сериями (runs), то он может быть отсортирован путем объединения этих серий. Произвольная строка не может быть просто разделена на две серии за один проход, но она может быть разделена на две строки, каждая из которых содержит несколько серий. Путем повторяющихся операций разделения и слияния может быть получена отсортированная строка. Покажем это на примере. Рассмотрим строку