Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 37
Текст из файла (страница 37)
Далее в главе 8 показано, что нижнюю границу П(п18п) можно превзойти, если информацию об отсортированном порядке входных элементов можно получить методами, отличными от попарного сравнения. Например, в алгоритме сортировки подсчетом предполагается, что входные данные образуют множество (О, 1,..., /с). Используя в качестве инструмента для определения относительного порядка элементов массива механизм индексации, алгоритм сортировки перечислением может отсортировать и чисел за время 9(/с + и). Таким образом, прн 7с = 0(п) время работы этого алгоритма линейно зависит от размера входного массива. Родственный алгоритм поразрядной сортировки может быть использован для расширения области применения сортировки перечислением.
Если нужно выполнить сортировку и целых чисел, каждое из которых имеет Н цифр, и при этом каждая цифра может принимать до Й возможных значений, то алгоритм поразрядной сортировки справится с этой задачей за время 9(с((п + 7с)). Если д является константой, а величина 1с ведет себя, как О(п), то время выполнения этого алгоритма линейно зависит от размера входного массива. Для применения третьего алгоритма — карманной сортировки — необходимы знания о распределе- Часть 71 Сортировка и яорясГковая статистика 177 нии чисел во входном массиве. Этот алгоритм позволяет выполнить сортировку и равномерно распределенных на полуоткрытом интервале [О, 1) действительных чисел за время 0(и) в среднем случае.
В следующей таблице содержится информация о времени работы алгоритмов сортировки из глав 2 и б — 8. Как обычно, и обозначает количество элементов, которые требуется отсортировать. В случае сортировки подсчетом сортируемыми элементами являются целые числа из множества (О, 1,..., к). В случае поразрядной сортировки каждый элемент представляет собой с1-значное число, причем каждая его цифра принимает Й различных значений. В карманной сортировке предполагается, что ключами являются равномерно распространенные на полуоткрытом интервале [О, 1) действительные числа.
В крайнем справа столбце приведено время работы алгоритма в среднем случае или ожидаемое время работы (с указанием вида времени работы в случае его отличия от времени работы в наихудшем случае). Время работы пирамидальной сортировки в среднем случае опущено, поскольку в данной книге оно не анализируется. Время работы Время работы в наихудшем в среднем случае случае!ожидаемое Алгоритм Порядковая статистика В множестве, состоящем из и чисел, 1-й порядковой статистикой называется г-е по величине значение в порядке возрастания. Конечно же, 1-ю порядковую статистику можно выбрать путем сортировки входных элементов и индексирования 1-го значения в выходных данных.
Если не делается никаких предположений о распределении входных элементов, время работы данного метода равно Й(и 18 и), как следует из величины нижней границы, найденной в главе 8. В главе 9 будет показано, что 1-й по величине (в порядке возрастания) элемент можно найти за время 0(и), даже если элементы представляют собой произвольные действительные числа. Мы представим рандомизированный алгоритм с компактным псевдокодом, время работы которого в наихудшем случае равно П(пз), но при этом его ожидаемое время работы равно 0(и). Мы также приведем более сложный алгоритм со временем работы 0(п) в наихудшем случае. Сортировка вставкой Сортировка слиянием Пирамидальная сортировка Быстрая сортировка Сортировка подсчетом Поразрядная сортировка Карманная сортировка П( 2) П(п 18 и) 0(и 18 п) П( 2) 9(й+ и) 9(с1(п + к)) со(пз) 6(п2) 6(п 18 п) 1Э(п 18 и) (ожидаемое) 6(к+ и) 9(с1(п + к)) кЭ(п) (в среднем случае) 17в Часть 1!.
Сортировка и лорлдковал статистика Теоретическая подготовка Хотя в основном в этой части не используется сложная математика, для освоения некоторых разделов требуется знание определенных разделов математики. В частности, в ходе анализа алгоритмов быстрой сортировки, карманной сортировки и алгоритма порядковой статистики используются некоторые положения теории вероятности, рассмотренные в приложении В, а также материал по вероятностному анализу и рандомизированным алгоритмам из главы 5. Анализ линейного алгоритма порядковой статистики в наихудшем случае содержит более сложные математические выкладки, чем используемые в ходе анализа наихудших случаев других рассмотренных в этой части алгоритмов. Глава 6.
Пирамидальная сортировка В этой главе описывается еще один алгоритм сортировки, а именно — пирамидальная сортировка. Время работы этого алгоритма, как и время работы сортировки слиянием (и в отличие от времени работы сортировки вставкой), равно 0(п1кп). Как и сортировка методом вставок, и в отличие от сортировки слиянием, пирамидальная сортировка выполняется без привлечения дополнительной памяти: в любой момент времени требуется память для хранения вне массива только некоторого постоянного количества элементов. Таким образом, в пирамидальной сортировке сочетаются наилучшие особенности двух рассмотренных ранее алгоритмов сортировки.
В ходе рассмотрения пирамидальной сортировки мы познакомимся с еще одним методом разработки алгоритмов, а именно — с использованием специализированных структур данных для управления информацией в ходе выполнения алгоритма. В рассматриваемом случае такая структура данных называется пирамидой (Ьеар) и может оказаться полезной не только при пирамидальной сортировке, но и при создании эффективной очереди с приоритетами. В последующих главах эта структура данных появится снова. Изначально термин "Ьеар" использовался в контексте пирамидальной сортировки (Ьеарзог1), но позже его основной смысл изменился, и он стал обозначать память со сборкой мусора, в частности в языках программирования (дзр и )ача (и переводиться как "куча"').
Однако в данной книге термину "Ьеар" (который здесь переводится как "пирамида") возвращен его первоначальный смысл.' 6.1. Пирамиды Структура данных ~бинарная) пирамида представляет собой объект-массив, который можно рассматривать как почти полное бинарное дерево (см. раздел Б.5.3), как показано на рис.6.1. Каждый узел этого дерева соответствует звпрочем, посюпьку перевод на русский язык термкна депр в контексте структур даннык и в контексте упрмюения памятью резвый, никекиа просегем неоднозначности у русскоязычного читатвы возникнуть не дмгино.
— Примеч. нер. (ВО Часть И. Сортировка и порядковая статвстаяа ! 1 3 4 5 ь 7 а 9 !о [(б(сс)ЧД[фГ8:..': Т: д'1Э Б', "-э4[ 1) (6) Рис. 6.1. Неаозрастающая пирамида, представленная в виде (а) бинарного дерева и в виде (б) массива Числа внутри кружков в каждом узле показьптют значение, хранящееся в ясом узле. Числа над узлами соответствуют индексам в массиве.
Линии ны( и под элементами массива показывают отношения между родительскими и дочерними узлами; родительские узлы всегда находятся левее дочерних. Высота дерева равна трем; узел с индексом 4 (и значением 8) имеет высоту 1. элементу массива. Дерево полностью заполнено на всех уровнях, за исключением, возможно, наинизшего, который заполняется слева направо. Массив А, представляющий пирамиду, является объектом с двумя атрибутами: А. (епд(Ь, (юторый, как обычно, дает количество элементов в массиве, и А.Ьеар-зтяе, который указывает, сколько элементов пирамиды содержится в массиве А.
Т.е. хотя А[1 .. А. (епд(Ь[ может содержать некоторые числа, только элементы подмассива А[1 .. А. Ьеар-вазе[, где О < А. Ьеар-закс < А. (епд(Ь, являются корректными элементами пирамиды. Корнем дерева является А[1], а для заданного индекса з узла можно легко вычислить индексы его родительского, левого и правого дочерних узлов. РАкехт[() 1 ге1пгп [з/2 [ $.ЕРТ(() 1 ге(нгп 2з Н!ОНТ(з) 1 ге(нгп 2!+ 1 На большинстве компьютеров операция 2! в процедуре 1.ерт выполняется с помощью одной команды процессора путем битового сдвига числа з на один бит влево. Аналогично операция 2! + 1 в процедуре ЮОНТ также выполняется очень быстро, путем сдвига бинарного представления числа з на одну позицию влево, а затем младший бнт устанавливается равным 1. Процедура РАкент выполняется путем сдвига числа з на один бит вправо. Эффективные программы пирамидальной сортировки часто реализуют эти процедуры как макросы или встраиваемые процедуры.
Различают два вида бинарных пирамид: неубывающие и невозрастающие. В пирамидах обоих видов значения, расположенные в узлах, удовлетворяют сиойснзву пирамиды (Ьеар ргорет(у), являющемуся отличительной чертой пирамиды !В! Глава д Пирамидапьиоа сортировка того или иного вида.
Свойства невазрастающик пирамид (шах-Беар ргорепу) заключается в том, что для каждого отличного от корневого узла с индексом г' выполняется неравенство А[РАкемт(1)] > А[1], т.е, значение узла не превышает значение родительского по отношению к нему узла. Таким образом, в невозрастающей пирамиде самый большой элемент находится в корне дерева, а значения узлов поддерева, берущего начало в каком-то элементе, не превышают значения самого этого элемента. Принцип организации неубывающей пирамиды (пнп-Ьеар) прямо противоположный.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
