Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Данные).pdf
Добавлен: 30.03.2023
Просмотров: 145
Скачиваний: 3
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
Выбираем в массиве некоторый элемент, который будем называть опорным элементом. Для корректности алгоритма значение этого элемента должно быть между максимальным и минимальным значениями в массиве (включительно). С точки зрения повышения эффективности алгоритма выгоднее всего выбирать медиану; но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. Часто хороший результат даёт выбор в качестве опорного элемента среднего арифметического между минимальным и максимальным элементами массива, особенно для целых чисел (в этом случае опорный элемент не обязан быть элементом сортируемого массива).
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
Вычисляется значение опорного элемента m по одной из стратегий.
Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше или равен опорному.
Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше или равен опорному.
Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает своё выполнение.
Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
Базой рекурсии являются наборы: пустой или состоящий из одного элемента, которые возвращаются в исходном виде. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно, и обработка гарантированно завершится.
Достоинства и недостатки
Достоинства:
Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
Прост в реализации.
Хорошо сочетается с механизмами кэширования и виртуальной памяти.
Допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах).
Допускает эффективную модификацию для сортировки по нескольким ключам (в частности — алгоритм Седжвика для сортировки строк): благодаря тому, что в процессе разделения автоматически выделяется отрезок элементов, равных опорному, этот отрезок можно сразу же сортировать по следующему ключу.
Работает на связных списках и других структурах с последовательным доступом, допускающих эффективный проход как от начала к концу, так и от конца к началу.
Недостатки:
- сильно деградирует по скорости при неудачных входных данных.
- прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека.
- неустойчив.
Улучшения
Улучшения алгоритма направлены, в основном, на устранение или смягчение вышеупомянутых недостатков, вследствие чего все их можно разделить на две группы: придание алгоритму устойчивости и «защита от худшего случая» — устранение деградации производительности и переполнения стека вызовов из-за большой глубины рекурсии при неудачных входных данных.
Что касается первой проблемы, то она элементарно решается путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация не бесплатна — она требует дополнительно памяти и одного полного прохода по массиву для сохранения исходных индексов.
Вторая проблема, в свою очередь, решается по двум разным направлениям: снижение вероятности возникновения худшего случая путём специального выбора опорного элемента и применение различных технических приёмов, обеспечивающих устойчивую работу на неудачных входных данных. Для первого направления:
Выбор среднего элемента. Устраняет деградацию для предварительно отсортированных данных, но оставляет возможность случайного появления или намеренного подбора «плохого» массива.
Выбор медианы из трёх элементов: первого, среднего и последнего. Снижает вероятность возникновения худшего случая, по сравнению с выбором среднего элемента.
Случайный выбор. Вероятность случайного возникновения худшего случая становится исчезающе малой, а намеренный подбор — практически неосуществимым.
Недостаток всех усложнённых методов выбора опорного элемента — дополнительные накладные расходы; впрочем, они не так велики.
Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:
При достижении нежелательной глубины рекурсии переходить на сортировку другими методами, не требующими рекурсии. Примером такого подхода является алгоритм Introsort. Можно заметить, что алгоритм очень хорошо подходит для такого рода модификаций, так как на каждом этапе позволяет выделить непрерывный отрезок исходного массива, предназначенный для сортировки, и то, каким методом будет отсортирован этот отрезок, никак не влияет на обработку остальных частей массива.
Модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах будет ограничена, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии. Правда, применение этого метода не спасёт от катастрофического падения производительности, но переполнения стека не будет.
Разбивать массив не на две, а на три части.
Глава 5. Сравнение алгоритмов сортировки
Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:
Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n).
Свойства и классификация
Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.
Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
Внутренняя сортировка оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат.
В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.
Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Объём данных не позволяет им разместиться в ОЗУ.
Также алгоритмы классифицируются по:
потребности в дополнительной памяти или её отсутствию;
потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой.
Итак, подытожим вышесказанное и выделим для каждого метода свои плюсы и минусы.
Пузырьковая сортировка:
+ быстро работает для почти отсортированных списков;
– медленно работает в остальных случаях.
Быстрая сортировка:
+ быстро сортирует большие списки;
– работает некорректно при большом количестве одинаковых значений.
Сортировка Шейкером:
+ сортирует данные на жёстком диске;
– работает медленнее, чем быстрая сортировка.
Метод Шелла:
+ сортирует дробные числа;
– требует много памяти для хранения временных значений.
Сортировка подсчётом:
+ очень быстро работает, если разброс входных значений не велик;
– медленно работает в случае если разброс составляет >log(N).
В настоящее время массивы данных достигают размеров, еще недавно казавшихся почти невероятными. В связи с этим требуется постоянная оптимизация используемых алгоритмов сортировки. Так же для некоторых целей больше подходят алгоритмы, не требующие большой скорости обработки и являющиеся более простыми.
Рост требований к скорости алгоритмов и расширению круга решения задач приводит к важной и актуальной задаче сравнительного анализа алгоритмов сортировки.
Для определения наиболее распространенных алгоритмов сортировки использована следующая классификация: алгоритмы устойчивой сортировки; алгоритмы неустойчивой сортировки; непрактичные алгоритмы сортировки; алгоритмы, не основанные на сравнениях и алгоритмы топологической сортировки.
При использовании устойчивой сортировки при наличии в массиве данных нескольких равных элементов в отсортированном наборе они останутся в том же порядке, что были в исходном наборе данных. К алгоритмам устойчивой сортировки относятся сортировка пузырьком, сортировка перемешиванием, гномья сортировка, сортировка вставками, сортировка слиянием, сортировка с помощью двоичного дерева, алгоритм сортировки Тима Петерса, сортировка подсчетом, блочная сортировка и некоторые другие.
Преимуществом устойчивой сортировки является сохранение взаимного расположения равных элементов, что важно при сортировке данных состоящих из нескольких полей. Недостатком является необходимость в дополнительной памяти и дополнительном времени сортировки.
При неустойчивой сортировке данные с одинаковыми значениями могут меняться местами. Основными алгоритмами неустойчивой сортировки являются сортировка Шелла, сортировка расческой, пирамидальная сортировка, плавная сортировка, быстрая сортировка, интроспективная сортировка, терпеливая сортировка, сортировка по частям и поразрядная сортировка.
Для неустойчивой сортировки необходимо меньше памяти и времени чем для устойчивой, но взаимное расположение равных элементов не сохраняется.
Непрактичные алгоритмы сортировки требуют большего времени, большей памяти либо специального аппаратного обеспечения. К ним относятся случайная сортировка (требует заметно большего времени, чем другие алгоритмы), глупая сортировка (эффективна для небольших массивов данных, при больших массивах требует значительных объемов дополнительной памяти), бисерная сортировка (медленный алгоритм, требующий дополнительной памяти и возможный для использования только для сортировки целых положительных чисел), блинная сортировка (требуется специальное аппаратное обеспечение).