В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 5
Текст из файла (страница 5)
Например, время сортировки массивов из 10000 элементовпримерно в 100 раз меньше.Хотя все эти алгоритмы весьма просты, их использование оправдано лишь для коротких массивов, поскольку средняя оценка трудоёмкости O(n2 ) становится неприемлемой для очень больших наборов данных. Длясортировки больших массивов существуют другие методы, которые мы рассмотрим далее.
Но тем не менее, рассмотренные выше алгоритмы не следует сбрасывать со счетов, так как они оказываются весьма эффективнымидля маленьких массивов именно за счет простоты своей логики. В качестве иллюстрации этого утвержденияможно привести следующую таблицу, в которой приведены результаты теста по сортировке 1000000 случайных10-элементных массивов.FindMax0.60Insert0.56BubbleDown0.36BubbleUp0.44OptFindMax0.65qsort1.59Хорошо видно, что функция qsort здесь не выдерживает конкуренции, а лучшим оказывается метод нисходящего пузырька, который был далеко не лучшим в сортировке длинных массивов.3.2.
Оценка снизу для трудоёмкости сортировокНам хотелось бы выяснить, с какой наименьшей гарантированной трудоёмкостью можно отсортировать массив.Теорема 3.1. Любой метод сортировки массива из n элементов, основанный на попарном сравнении элементов, не может иметь гарантированную оценку трудоёмкости лучше, чем O(n log2 n) сравнений. Рассмотрим произвольный сортирующий алгоритм A, основанный на попарном сравнении элементов.Будем считать, что A сортирует массивы из n элементов. Ясно, что A состоит их серии элементарных шагов, гдекаждый шаг состоит в сравнении некоторых двух элементов массива и возможном выполнении перестановкикаких-то элементов.
После завершения очередного шага алгоритм переходит к следующему шагу, т. е. сравниваетдругие элементы, выполняет перестановку, если это необходимо, и т. д. В результате подобная серия шаговзавершается получением упорядоченного массива.Отсюда следует, что A можно представить в виде бинарного дерева, где каждая вершина соответствуетоперации сравнения некоторых элементов, а потомки вершины соответствуют последующим шагам, которыеследует выполнить в зависимости от того или иного результата этой операции сравнения.Таким образом, подавая на вход A некоторый массив, мы выполняем сравнения, предписанные вершинам,начиная с корня дерева, и спускаемся по некоторой ветви к концевой вершине, получая в результате упорядоченный массив.1 Времяв секундах, компилятор GCC 3.2, Intel Pentium IV, 2.0 GHz13Сортировка каждого конкретного входного массива будет соответствовать проходу, вообще говоря, по своейветви. Отсюда количество концевых вершин дерева будет равно количеству различных перестановок n элементов, т.
е. n!.Для бинарного дерева заданной глубины h максимальное количество концевых вершин соответствует идеально сбалансированному дереву и равно 2h . Следовательно, обозначив через h глубину дерева для A, мы имеемнеравенство 2h > n!. Заметим, что гарантированное время работы алгоритма есть глубина дерева.Для оценки воспользуемся формулой Стирлинга:2h > n! ≈√12π ·nn+ 2,enn−→ ∞.Логарифмируя это соотношение и оставляя главный член относительно n, получаем искомую оценку h > C ·n log2 n, где C — некоторая константа.
Эта теорема устанавливает ориентир, на который надо равняться при выборе или разработке универсальныхметодов сортировки. Таким образом, если некоторый метод сортировки обеспечивает трудоёмкость порядкаn log2 n, то его следует признать оптимальным по порядку и борьба может идти лишь за возможно более малуюконстанту в выражении O(n log2 n).
Ниже мы рассмотрим два метода, реализующие подобную оптимальнуюоценку трудоёмкости.3.3. Быстрая сортировкаАлгоритм быстрой сортировки был предложен в 1962 году Ч. Хоаром (C. Hoare). Поскольку этот алгоритмпродемонстрировал высокую скорость работы, он был назван быстрой сортировкой (quicksort).
Хотя гарантированная оценка производительности этого алгоритма тоже составляет O(n2 ) операций, подавляющее большинствомассивов он сортирует с затратами порядка O(n log2 n). Подобная эффективность привела к тому, что сортировки на основе этого алгоритма были включены в различные пакеты стандартных программ (в частности, встандартной библиотеке C и C++ он реализован в виде функции qsort).Идея алгоритма состоит в разделении специальным образом исходного массива на две части и дальнейшейрекурсивной сортировке каждой из этих частей.
Опишем идею более формально.Итак, пусть мы имеем неупорядоченный массив a0 , . . . , an−1 и некоторое число m, которое удовлетворяетусловию min ai 6 m 6 max ai . Перестроим массив так, чтобы при некотором 0 6 s 6 n − 1 были выполненыiiусловия ai 6 m при i 6 s и ai > m при i > s. Для этого последовательно сравнивая элементы массива aj ,j = 0, 1, . . . с m, найдем первое значение j, при котором aj > m. Теперь последовательно сравнивая элементымассива ak с числом m, где k = n − 1, n − 2, .
. . , двигаясь от конца к началу, мы либо найдем k : ak 6 m иk > j, либо получим k = j. Если j < k, то обмениваем местами элементы aj и ak и повторяем описанную вышепроцедуру для элементов массива aj+1 , . . . , ak−1 . Если k = j, то мы получили искомое разбиение массива на дветребуемых части при s = k.Теперь рекурсивно применим описанную выше процедуру для каждой из полученных частей массива (естественно, с соответствующим новым значением m). После завершения всех рекурсивных вызовов массив будетупорядочен.Заметим, что трудоёмкость алгоритма сильно зависит от удачного выбора числа m, поскольку именно оноопределяет позицию, где массив будет разделен на две части.
Если это разделение каждый раз происходитпримерно посередине, то трудоёмкость составляет O(n log2 n) операций, однако, если разделение каждый разотщепляет только один элемент, то трудоёмкость составит O(n2 ) операций.Оптимальным выбором m является медиана массива, т. е. такое число, что массив разбивается этим числомпримерно пополам.
Проблема заключается в том, что его нельзя быстро найти. Неплохие результаты получаются, когда в качестве m берется среднее арифметическое нескольких (двух-трёх) элементов рассматриваемойчасти массива.Заметим также, что при рекурсии первой следует обрабатывать часть массива, имеющую меньшую длину,так как это гарантирует, что глубина рекурсии не превысит log2 n.Выше уже было заявлено, что подавляющее большинство массивов быстрая сортировка сортирует быстро.Настало время доказать это.Теорема 3.2. Для массивов из n элементов быстрая сортировка обеспечивает среднюю трудоёмкостьO(n log2 n) операций.
Определимся с понятием средней трудоёмкости. Как видно из описания алгоритма, трудоёмкость алгоритма зависит от того, в какой позиции текущего массива происходит разделение на левую и правую части дляпоследующего рекурсивного вызова. Будем считать, что эта позиция может равновероятно оказаться в любомместе массива и будем оценивать трудоёмкость как среднее значение для всех возможных исходов. Обозначим14через Tn среднюю трудоёмкость сортировки массива из n элементов. Эта трудоёмкость складывается из операций по разделению массива на две части, что требует порядка n операций, и трудоёмкости сортировок двухподмассивов длины k и n − k, где k — позиция разделения.Следуя нашему определению средней трудоёмкости, получаем оценкуTn 6 cn +n−1n−11 X2 X(Tk + Tn−k ) = cn +Tk ,n−1n−1k=1k=1где c — некоторая константа.Докажем, что можно выбрать константы a, b ∈ N, так, что ∀ n ∈ N будет выполненоTn 6 a · n log2 n + b.Доказательство проведем по индукции.
База индукции n = 1 очевидна. Действительно, массив из одногоэлемента сортировать не надо, и мы можем считать, что требуемое неравенство выполнено при b = 1: этаединственная операция нужна, чтобы при выполнении алгоритма сравнить n с числом 1.Пусть теперь n > 1 и пусть указанное неравенство верно для m < n, докажем его справедливость для m = n.Используя предположение индукции и интегрирование по частям, получаемn−1Xk=1Tk 6n−1Xk=1a(ak log2 k + b) 6ln 2Zn1 na x21x ln xdx + b(n − 1) =ln x −+ b(n − 1).ln 2 22 1Подставляем эту оценку в исходное неравенство и, пользуясь тем, что n 6 2n − 2 при n > 1, получаемaaan2 ln nan2a n2 ln n − 21·+= cn + 2b ++·−·6Tn 6 cn + 2b +ln 2n−12 ln 22 ln 2 2 ln 2 n − 12 ln 2 n − 1aana 6 cn + 2b ++ an log2 n −= an log2 n + b + b + n c −.2 ln 22 ln 22 ln 2Теперь ясно, что если мы возьмём b = 1 и a > 2(c + 1) ln 2, то требуемое неравенство будет выполнено, ибопри таких a и b последняя скобка станет отрицательной.
Но полученная оценка в точности и означает, что времяработы алгоритма есть O(n log2 n). 3.4. Пирамидальная сортировка (HeapSort)Это один из самых эффективных алгоритмов, дающих гарантированное время сортировки O(n log2 n). Кроме того, он нетребует дополнительной памяти. Разложим элементы массивав узлы бинарного дерева, двигаясь сверху вниз, слева направо,a1a2как показано на рисунке.
Таким образом, дерево будет абсолютно сбалансированным, если в массиве 2k −1 элемент (т. е. длиныa3a4a5a6всех веток, идущих от корня, равны). В остальных случаях впоследнем уровне дерева будут заняты первые n − 2k−1 + 1 листьев. В этих формулах k — глубина дерева. Назовём деревоa7a8a9a10a11пирамидой, если значение в любой вершине, имеющей детей,не меньше значений детей. Покажем, что можно построить пирамиду из исходного массива не более, чем за O(n log2 n) шагов. Назовём семьёй элемент дерева и его детей.Пусть элементы массива ak+1 , .
. . , an−1 удовлетворяют пирамидальному свойству. Будем просеивать элементak . Пусть aj есть максимум в семье ak . Тогда, если ak < aj , то поменяем местами ak и aj , иначе закончим процесспросеивания. После перестановки наш бывший k-й элемент сполз на 1 уровень дерева вниз. Будем повторятьнашу процедуру просеивания для этого элемента, пока он не сползёт на самый нижний уровень дерева или невозникнет ситуация, когда он станет максимумом в своей семье. Заметим, что в процессе упорядочения семьиродителем становится максимум среди семьи.Очевидно, что в процессе такого просеивания элементы ak , . . . , an−1 станут обладать пирамидальной структурой. Просеивая далее элемент ak−1 , затем ak−2 и т.
д., мы придём к пирамиде. Очевидно,что начинать просеивание можно с той вершины, которая ещё имеет детей, т. е. вершины с номером n−2. Процесс просеивания2одного элемента занимает не более log2 n операций, поскольку количество возможных перестановок не превосходит глубины дерева. Далее, весь процесс построения пирамиды занимает не более n log2 n операций, посколькув худшем случае придётся просеять всё дерево за исключением одного элемента.Имея пирамиду, мы без труда отсортируем массив.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
