Файл: Сортировка слиянием.pdf

2.4. Быстрая сортировка

Метод быстрой сортировки был впервые описан Ч.А.Р. Хоаром в 1962 году. Быстрая сортировка – это общее название ряда алгоритмов, которые отражают различные подходы к получению критичного параметра, влияющего на производительность метода.

Быстрая сортировка популярна, прежде всего, потому, что ее нетрудно реализовать, она хорошо работает на различных видах входных данных и во многих случаях требует меньше ресурсов по сравнению с другими методами сортировки [4, С. 62].

Алгоритм быстрой сортировки обладает и другими привлекательными особенностями: он принадлежит к категории обменных сортировок (использует лишь небольшой вспомогательный стек), на упорядочение N элементов в среднем затрачивает время, пропорциональное N log N, и имеет исключительно короткий внутренний цикл. Его недостатком является то, что он неустойчив, выполняет в худшем случае N 2 операций и ненадежен в том смысле, что простая ошибка в реализации может остаться незамеченной, но существенно понизить производительность на некоторых видах файлов [4, С. 64].

Работа быстрой сортировки проста для понимания. Алгоритм был подвергнут тщательному математическому анализу, и существуют точные оценки его эффективности. Этот анализ был подтвержден обширными эмпирическими экспериментами, а сам алгоритм отшлифован до такой степени, что ему отдается предпочтение в широком диапазоне практических применений сортировки. Поэтому эффективной реализации алгоритма быстрой сортировки стоит уделить гораздо большее внимание, чем реализациям других алгоритмов. Аналогичные методы реализации пригодны и для других алгоритмов; но для быстрой сортировки их можно применять с полной уверенностью, поскольку точно известно их влияние на эффективность сортировки [4, С. 64].

Многие пытаются разработать способы улучшения быстрой сортировки: ускорение алгоритмов сортировки играет роль "изобретения велосипеда" в компьютерных науках, а быстрая сортировка представляет собой почтенный метод, который так и хочется улучшить. Его усовершенствованные версии стали появляться в литературе практически с момента опубликования Хоаром. Предлагалось и анализировалось множество идей, но при оценке этих улучшений легко ошибиться, поскольку данный алгоритм настолько удачно сбалансирован, что небольшое усовершенствование одной части программы может привести к резкому ухудшению работы другой ее части [10, С. 299].

Тщательно настроенная версия быстрой сортировки обычно работает быстрее любого другого метода сортировки на большинстве компьютеров, поэтому быстрая сортировка широко используется как библиотечная программа сортировки и в других серьезных приложениях сортировки. Утилита сортировки из стандартной библиотеки С++ называется qsort, т.к. ее различные реализации обычно основаны на алгоритме быстрой сортировки. Однако время выполнения быстрой сортировки зависит от организации входных данных и колеблется между линейной и квадратичной зависимостью от количества сортируемых элементов, и пользователи иногда бывают неприятно удивлены неожиданно неудовлетворительной работой сортировки на некоторых видах входных данных, особенно при использовании хорошо отлаженных версий этого алгоритма. Если приложение работает настолько плохо, что возникает подозрение в наличии дефектов в реализации быстрой сортировки, то более надежным выбором может оказаться сортировка Шелла, хорошо работающая при меньших затратах на реализацию. Однако в случае особо крупных файлов быстрая сортировка обычно выполняется в пять-десять раз быстрее сортировки Шелла, а для некоторых видов файлов, часто встречающихся на практике, ее можно адаптировать для еще большего повышения эффективности [10, С. 300].

Алгоритм быстрой сортировки Хоара - пусть дан массив x[n] размерности n.

Шаг 1. Выбирается опорный элемент массива.

Шаг 2. Массив разбивается на два – левый и правый – относительно опорного элемента. Реорганизуем массив таким образом, чтобы все элементы, меньшие опорного элемента, оказались слева от него, а все элементы, большие опорного – справа от него.

Шаг 3. Далее повторяется шаг 2 для каждого из двух вновь образованных массивов. Каждый раз при повторении преобразования очередная часть массива разбивается на два меньших и т. д., пока не получится массив из двух элементов (рис. 7).

Быстрая сортировка стала популярной прежде всего потому, что ее нетрудно реализовать, она хорошо работает на различных видах входных данных и во многих случаях требует меньше затрат ресурсов по сравнению с другими методами сортировки [6, С. 462].

Выберем в качестве опорного элемент, расположенный на средней позиции.

Рис. 7. Демонстрация быстрой сортировки Хоара по неубыванию

Эффективность быстрой сортировки в значительной степени определяется правильностью выбора опорных (ведущих) элементов при формировании блоков. В худшем случае трудоемкость метода имеет ту же сложность, что и пузырьковая сортировка, то есть порядка O(n2). При оптимальном выборе ведущих элементов, когда разделение каждого блока происходит на равные по размеру части, трудоемкость алгоритма совпадает с быстродействием наиболее эффективных способов сортировки, то есть порядка O(n log n). В среднем случае количество операций, выполняемых алгоритмом быстрой сортировки, определяется выражением T(n) = O(1.4n log n) [4, С. 64].

Размер стека. Для быстрой сортировки можно применить явный стек магазинного типа, используя его для хранения информации о еще не обработанных подфайлах, которые ожидают сортировки. Каждый раз, когда нужно обработать подфайл, он выталкивается из стека. При разбиении файла получаются два не обработанных подфайла, и они помещаются в стек [10, С. 309].

Для случайно упорядоченных файлов максимальный раздел стека пропорционален log N, но в вырожденных случаях стек может вырасти до размера, пропорционального N, что показано на рис. 8. Ведь наихудший случай - это когда входной файл уже отсортирован. Потенциальная возможность роста стека до размера, пропорционального размеру входного файла представляет собой не очевидную, но вполне реальную проблему для рекурсивной реализации быстрой сортировки: стек, пусть и неявно, используется всегда, а вырожденный файл большого размера может стать причиной аварийного завершения программы из-за нехватки памяти. Конечно, для библиотечной программы сортировки такое поведение недопустимо. На самом деле программе скорее не хватит времени, чем памяти [10, С. 310].

Рис. 8. Размер стека при работе быстрой сортировки

Рекурсивный стек для быстрой сортировки не бывает большим при обработке случайно упорядоченных файлов, но в вырожденных случаях он может занимать очень большой объем памяти. Здесь приведены графики размеров стека для двух случайно упорядоченных файлов (слева и в центре) и для частично упорядоченного файла (справа).

Трудно гарантированно исключить такое поведение программы, но в полнее вероятно предусмотреть специальные средства, которые сведут вероятность возникновения таких вырожденных случаев почти к нулю.

На рис. 9 показана стратегия, которая решает эту проблему, проверяя размеры обоих подфайлов и первым помещая в стек больший из них. Сравнивая данный пример с приведенным на рис. 7, можно увидеть, что это правило не изменяет подфайлы, меняется лишь порядок их обработки. Так это экономит память без изменения времени выполнения [410, С. 310].

Нерекурсивная быстрая сортировка. Данная нерекурсивная реализация быстрой сортировки использует явный стек магазинного типа, заменяя рекурсивные вызовы помещением в стек параметров, а рекурсивные вызовы процедур и выходы из них - циклом, выталкивающим параметры из стека и обрабатывающим их, пока стек не пуст. Больший из двух подфайлов помещается в стек первым, чтобы максимальная глубина стека при сортировке N элементов не превосходила lgN [10, С. 310].

Рис. 9. Пример работы быстрой сортировки (вначале упорядочивается меньший подфайл)

Порядок обработки подфайлов не влияет ни на корректность работы алгоритма быстрой сортировки, ни на время выполнения, однако он может повлиять на размер стека, необходимого для поддержки рекурсивной структуры. Здесь после каждого разбиения вначале обрабатывается меньший из двух подфайлов.

Правило, согласно которому больший из двух подфайлов помещается в стек первым, обеспечивает, что каждый элемент стека имеет размер, не больший половины элемента под ним, так что стеку нужна память только для порядка lgN элементов. Это максимальное заполнение стека имеет место, если разбиение всегда попадает в центр файла. Для случайно упорядоченных файлов реальный максимальный размер стека гораздо меньше; для вырожденных файлов он обычно мал.

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

Рекурсивная реализация быстрой сортировки позволяет устранить этот недостаток путем включения прямого метода сортировки для частей массива с небольшим количеством элементов. Анализ вычислительной сложности таких алгоритмов показывает, что если подмассив имеет девять или менее элементов, то целесообразно использовать прямой метод (сортировку простыми вставками) [10, С. 311].

2.5. Сортировка слиянием

Алгоритм сортировки слиянием был изобретен Джоном фон Нейманом в 1945 году. Он является одним из самых быстрых способов сортировки.

Слияние – это объединение двух или более упорядоченных массивов в один упорядоченный [6, С. 423].

Сортировка слиянием является одним из самых простых алгоритмов сортировки (среди быстрых алгоритмов). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске). Кроме того, сортировка слиянием является алгоритмом, который может быть эффективно использован для сортировки таких структур данных, как связанные списки [6, С. 425].

Данный алгоритм применяется тогда, когда есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива. Он построен на принципе "разделяй и властвуй". Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Далее их решения комбинируются, и получается решение исходной задачи (рис. 10).

Процедура слияния требует два отсортированных массива. Заметим, что массив из одного элемента по определению является отсортированным.

Алгоритм сортировки слиянием

Шаг 1. Разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары).

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

Шаг 3. Если число отсортированных цепочек больше единицы, перейти к шагу 2.

Рис. 10. Демонстрация сортировки слиянием по неубыванию

Недостаток алгоритма заключается в том, что он требует дополнительную память размером порядка n (для хранения вспомогательного массива). Кроме того, он не гарантирует сохранение порядка элементов с одинаковыми значениями. Но его временная сложность всегда пропорциональна O(n log n) [6, С. 425].

Выборка и слияние - противоположные операции в том смысле, что выборка разбивает файл на два независимых файла, а слияние объединяет два независимых файла в один. Контраст между этими двумя операциями становится очевидным при применении принципа «разделяй и властвуй» для создания конкретных методов сортировки. Можно переупорядочить файл таким образом, что если отсортировать обе части файла, становится упорядоченным и весь файл; и наоборот, можно разбить файл на две части, отсортировать их, а затем объединить упорядоченные части и получить весь файл в упорядоченном виде. В первом случае получается: быстрая сортировка, состоящая из процедуры выборки, за которой следуют два рекурсивных вызова [6, С. 425]. Далее рассмотрим сортировку слиянием (mergesort), которая является противоположностью быстрой сортировки, поскольку состоит из двух рекурсивных вызовов с последующей процедурой слияния.

Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует файл, состоящий из N элементов, за время, пропорциональное N logN, независимо от характера входных данных.

Основной недостаток сортировки слиянием заключается в том, что простые реализации этого алгоритма требуют объема дополнительной памяти, пропорционального N. Это препятствие можно преодолеть, однако способы сделать это настолько сложны, что практически неприменимы, особенно если учесть, что можно воспользоваться пирамидальной сортировкой. Кодирование сортировки слиянием не труднее кодирования пирамидальной сортировки, а длина ее внутреннего цикла находится между аналогичными показателями быстрой сортировки и пирамидальной сортировки; так что сортировка методом слияния достойна внимания, если важно быстродействие, недопустимо ухудшение производительности на " неудобных " входных данных и доступна дополнительная память [10, С. 331].