Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 48
Текст из файла (страница 48)
Согласно Кнуту, сортировка подсчетом впервые была предложена Севардом (Н.Н. Бевап1) в 1954 году; ему также принадлежит идея объединения сортировки Глава 8. Сортировка за линейное время 239 подсчетом и поразрядной сортировки. Оказывается, что поразрядная сортировка, начинающаяся с самой младшей значащей цифры, — по сути "народный" алгоритм, широко применявшийся операторами механических машин, предназначенных для сортировки перфокарт. Как утверждает Кнут, первая ссылка на этот метод появилась в документе, составленном Комри (ЬЗ. Сошпе) и опубликованном в 1929 году, где описывается счетно-перфорационное оборудование. Карманная сортировка используется с 1956 года, с того времени, когда Исаак (ЕЗ. 1заас) и Синглтон (К.С.
8!пй!е!оп) предложили основную идею этого метода. Мунро (Мишо) и Раман (Кашен) [229] предложили устойчивый алгоритм сортировки, который в наихудшем случае выполняет О (п1+') сравнений, где 0 < < в < 1 — произвольная константа. Несмотря на то, что в алгоритмах, время выполнения которых равно О (и 18 п), выполняется меньше сравнений, в алгоритме Мунро н Рамана данные перемещаются О (и) раз, и он выполняет сортировку на месте. Случай сортировки п 6-битовых чисел за время о (п1к и) рассматривался многими исследователями. Было получено несколько положительных результатов, в каждом из которых незначительно менялись предположения о вычислительной модели, а также накладываемые на алгоритм ограничения. Во всех случаях предполагалось, что память компьютера разделена на адресуемые 6-битовые слова.
Фредман (РгесЬпап) и Виллард (9У!1!агд) [99] первыми предложили использовать дерево слияний (Гпз!оп !гее) и выполнять с его помощью сортировку и целых чисел за время О (и 1к и/18!к п). Впоследствии эта граница была улучшена Андерссоном (Апдегззоп) [16] до О (пайп). В этих алгоритмах применяется операция умножения, а также некоторые предварительно вычисляемые константы. Андерссон, Хейгерап (Найегпр), Нильсон (1%!эзоп) и Раман [17] показали, как выполнить сортировку п чисел за время О (и 1к 1к п), не используя при этом умножение, однако этот метод требует дополнительной памяти, обьем которой увеличивается с ростом и.
С помощью мультипликативного хеширования объем этого пространства можно уменьшить до величины О (и), но при этом граница для наихудшего случая О (п18!ко) становится границей для математического ожидания времени работы. Обобщив экспоненциальные деревья поиска, Андерссон [16] и Торуп (Т!зогцр) [297] сформулировали алгоритм сортировки, выполняющийся в течение времени О (и (18!ко) ).
В этом алгоритме не используется ни умножение, нн рандомизация, а обьем необходимой дополнительной памяти линейно зависит от количества элементов. Дополнив эти методы новыми идеями, Хан (Нап) [137] улучшил границу времени работы до О (п 18 18 и 18 18 18 и). Несмотря на то, что упомянутые алгоритмы стали важным теоретическим достижением, все они чрезвычайно сложные, и в данный момент представляется маловероятным, чтобы они могли практически составить конкуренцию существующим алгоритмам сортировки.
ГЛАВА 9 Медианы и порядковые статистики Будем называты-й порядковой статистикой (огбег ьтабзбс) множества, состоящего из и элементов, (-й элемент в порядке возрастания. Например, минимум такого множества — это первая порядковая статистика (г = 1), а его максимум— это и-я порядковая статистика (( = п). Медиана (шеб(ап) неформально обозначает середину множества.
Если и нечетное, то медиана единственная, и ее индекс равен ю' = (и + 1)/2; если же п четное, то медианы две, и их индексы равны г = п/2 и г = и/2+ 1. Таким образом, независимо от четности и, медианы располагаются при г = '1(п + 1)/2! (нижняя медиана (!ожег шейап)) и г = ! (и + 1)/21 (верхняя медияия (иррег тейап)). Однако в этой книге для простоты используется выражение "медиана", которое относится к нижней медиане. Данная глава посвящена проблеме выбора г-й порядковой статистики в множестве, состоящем из п различных чисел.
Для удобства предположим, что все числа в множестве различны, хотя почти все, что мы будем делать, обобщается на случай, когда некоторые значения в множестве повторяются. Формально задачу выбора (зе(есбоп ргоЫеш) можно определить следующим образом. Вход: множество А, состоящее из и (различных) чисел, и число 1 < г < и. Выход: элемент к е А, превышающий по величине ровно г — 1 других элементов множества А. Задачу выбора можно решить за время О (п!кп). Для этого достаточно выполнить сортировку элементов с помощью пирамидальной сортировки или сортировки слиянием, а затем просто извлечь элемент выходного массива с индексом з.
Однако есть и более быстрые алгоритмы. В разделе 9.1 рассматривается задача о выборе минимального и максимального элементов множества. Больший интерес представляет общая задача выбора, Глава 9. Медианы и порядковые статистики 241 которая исследуется в двух последующих разделах. В разделе 9.2 анализируется применяющийся на практике алгоритм, время работы которого в среднем составляет О (п) (предполагается, что все элементы различны). В разделе 9.3 приведен алгоритм, представляющий больший практический интерес, время работы которого достигает величины О (и) в наихудшем случае.
9.1 Минимум и максимум Сколько сравнений необходимо для того, чтобы найти минимальный элемент в и-элемеитном множестве? Для этой величины легко найти верхнюю границу, равную п — 1 сравнениям: мы по очереди проверяем каждый элемент множества и следим за тем, какой из них является минимальным на данный момент. В представленной ниже процедуре предполагается, что исследуется множество, состоящее из элементов массива А, где 1епутл [А] = п: мммим(А) 1 пнп ~ — А[Ц 2 аког г' — 2 1о 1епдй[А] 3 до и тгп ) А[т] 4 тпеп тгп - А[1] 5 гегнгп тгп Очевидно, что для поиска максимального элемента также понадобится не более п — 1 сравнений. Является лн представленный выше алгоритм оптимальным? Да, поскольку можно доказать, что нижняя граница для задачи определения минимума также равна и — 1 сравнений.
Любой алгоритм, предназначенный для определения минимального элемента множества, можно представить в виде турнира, в котором принимают участие все элементы. Каждое сравнение — зто поединок между двумя элементами, в котором побеждает элемент с меньшей величиной. Важное наблюдение заключается в том, что каждый элемент, кроме минимального, должен потерпеть поражение хотя бы в одном поединке. Таким образом, для определения минимума понадобится и — 1 сравнений, и алгоритм Мп п~мцм является оптимальным по отношению к количеству производимых в нем сравнений. Одновременный поиск минимума и максимума В некоторых приложениях возникает необходимость найти как минимальный, так и максимальный элементы множества. Например, графической программе может понадобиться выполнить масштабирование множества координат (х, у) таким образом, чтобы они совпали по размеру с прямоугольной областью экрана или Часть И.
Сортировка и порядковая статистика 242 другого устройства вывода. Для этого сначала надо определить максимальную и минимальную координаты. Несложно разработать алгоритм для поиска минимума и максимума в и-элементном множестве, производя при этом О (и) сравнений; при этом алгоритм будет асимптотически оптимальным. Достаточно просто выполнить независимый поиск минимального и максимального элементов. Для выполнения каждой подзадачи понадобится и — 1 сравнений, что в сумме составит 2и — 2 сравнений. Однако на самом деле для одновременного определения минимума и максимума достаточно не более 3 (п/21 сравнений. Для этого необходимо следить за тем, какой из проверенных на данный момент элементов минимальный, а какой— максимальный. Вместо того, чтобы отдельно сравнивать каждый входной элемент с текущим минимумом и максимумом (для чего пришлось бы на каждый элемент израсходовать по два сравнения), мы будем обрабатывать пары элементов.
Образовав пару входных элементов, сначала сравним их один с другим, а затем меньший элемент пары будем сравнивать с текущим минимумом, а больший— с текущим максимумом. Таким образом, для каждой пары элементов понадобится по 3 сравнения. Способ начального выбора текущего минимума и максимума зависит от четности количества элементов в множестве и. Если п нечетно, мы выбираем из множества один из элементов и считаем его значение одновременно и минимумом, н максимумом; остальные элементы обрабатываем парами.
Если же и четно, то выбираем два первых элемента и путем сравнения определяем, значение какого из них будет минимумом, а какого — максимумом. Остальные элементы обрабатываем парами, как н в предыдущем случае. Проанализируем, чему равно полное число сравнений. Если п нечетно, то нужно будет выполнить 3 (и/21 сравнений. Если же п четно, то выполняется одно начальное сравнение, а затем — еще 3 (и — 2)/2 сравнений, что в сумме дает Зи/2 — 2 сравнений.
Таким образом, в обоих случаях полное количество сравнений не превышает 3 (п/21. Упражнения 9.1-1. Покажите, что для поиска второго в порядке возрастания элемента в наихудшем случае достаточно и + ~1~ п1 — 2 сравнений. (Указание: найдите заодно и наименьший элемент.) 9.1-2. Покажите, что в наихудшем случае для поиска максимального и минимального среди и чисел необходимо выполнить ~Зп/21 — 2 сравнений. (Указание: рассмотрите вопрос о том, сколько чисел являются потенциальными кандидатами на роль максимума или минимума, и определите, как на это количество влияет каждое сравнение.) Глава 9.
Медианы и порядковые статистики 243 9.2 Выбор в течение линейного ожидаемого времени Общая задача выбора оказывается более сложной, чем простая задача поиска минимума. Однако, как это ни странно, время решения обеих задач в асимптотическом пределе ведет себя одинаково — как О (п). В данном разделе вниманию читателя представляется алгоритм типа "разделяй и властвуй" КлнпОм12еп Бе~.ест, предназначенный для решения задачи выбора. Этот алгоритм разработан по аналогии с алгоритмом быстрой сортировки, который рассматривался в главе 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
