II Сортировка и порядковые статистики

Введение

В этой части мы рассмотрим несколько алгоритмов, решающих задачу сортировки (sorting problem). Исходным данным для этой задачи является последовательность чисел (а\, а2, ., ап). Результатом должна быть последовательность (at, а2,..., ап), состоящая из тех же чисел, идущих в неубывающем порядке: а[ а2 • • • ап. Обычно исходная последовательность задана как массив, хотя возможны и другие варианты (например, связанный список).

Структура сортируемых объектов

На практике редко требуется упорядочивать числа как таковые. Обычно надо сортировать записи (records), содержащие несколько полей, и располагать их в порядке, определяемым одним из полей. [Например, в архиве отдела кадров для каждого сотрудника фирмы может храниться запись, содержащая различные поля (фамилия, имя, отчество, год рождения, адрес и т.п.), и в какой-то момент может понадобиться упорядочить все записи по годам рождения.] Поле, по которому проводится сортировка (год рождения в нашем примере), называется ключом (key), а остальные поля - дополнительными данными (satellite data). Можно представлять себе дело так: алгоритм сортирует ключи, но вместе с каждым ключом перемещаются (без изменения) дополнительные данные, с ним связанные. (Если этих данных много, разумно перемещать не сами данные, а лишь указатель на них.)

Все эти подробности мы не рассматриваем, ограничиваясь задачей сортировки ключей. Приводимые нами алгоритмы являются, таким образом, лишь «скелетом» реальной программы, к которому нужно добавить обработку дополнительных данных (что обычно не сложно, хотя и хлопотно).

Алгоритмы сортировки

Мы уже встречались в главе 1 с двумя алгоритма, сортирующими га чисел за время ©(га2) в худшем случае. Их простота, однако, делает их эффективными для сортировки небольшого массива без дополнительной памяти (in place). (Имеется в виду, что мы не имеем права заводить ещё одного массива, но переменные для чисел использовать можно). Алгоритм сортировки слиянием имеет лучшую асимптотическую оценку времени работы, но он требует дополнительного массива.

В этой части книги мы рассмотрим ещё два алгоритма сортировки вещественных чисел. Первый из них называется «сортировкой с помощью кучи» (heapsort). Здесь «куча» - некоторая структура данных, имеющая много приложений (одно из них, очереди с приоритетами, мы также рассмотрим в главе 7). Этот алгоритм не требует дополнительного массива и работает за время ©(га lgra) в худшем случае.

В главе 8 строится другой алгоритм, называемый «быстрой сортировкой» (quicksort). В худшем случае он требует времени 0(га2), но в среднем - лишь в (га lgra), и на практике он обычно быстрее сортировки с помощью кучи (его внутренний цикл прост, поэтому константа в асимптотической оценке меньше).

Все эти алгоритмы (сортировки вставками, слиянием, с помощью кучи и быстрая сортировка) используют только попарные сравнения объектов, но не их внутреннюю структуру. В главе 9 мы показываем, что любая сортировка такого вида в худшем случае требует времени Q(гаlgra), введя подходящую формальную модель (разрешающие деревья). Тем самым становится ясным, что сортировки слиянием и с помощью кучи асимптотически оптимальны.

Однако эта нижняя оценка не распространяется на алгоритмы, использующие внутреннюю структуру данных. В главе 9 рассматривается несколько примеров такого рода. Сортировка подсчётом (counting sort) позволяет отсортировать га целых чисел в диапазоне от 1 до к за время 0(п-\-к), используя сортируемые числа как индексы в массиве размера к. Если к = О (га), время сортировки становится пропорциональным размеру массива. Родственный алгоритм, называемый «цифровой сортировкой», применяет сходный приём поразрядно, и позволяет отсортировать га целых чисел, каждое из которых имеет d разрядов в /г-ичной системе счисления, за время 0(d(n-\-k)). Если считать, что d постоянно, а к есть О(п), то общее время есть О (га). Третий алгоритм такого рода, сортировка вычерпыванием, предполагает, что сортируемые числа равномерно распределены на отрезке и независимы, и в среднем требует О (га) действий для га чисел.