Сортировка вставками со сторожевым элементом доклад
Обновлено: 02.07.2024
Упорядочить массив x по убыванию или возрастанию (т.е. переставить его элементы так чтобы для всех k выполнялось xk =xk-1 соответственно), используя следующий алгоритм сортировки (упорядочивания):
сортировка вставками : пусть первые k элементов массива уже упорядочены по не убыванию; берется (k +1)-й элемент и размещается среди первых k элементов так, чтобы упорядоченными оказались уже k +1 первых элементов; этот метод применяется при k от 1 до n-1.
Основные требования к программе:
· В программе должны использоваться функции, для которых следует явно сопоставить прототипы (объявления, описания), определения и вызовы.
· Как минимум в одной функции должны быть параметры по умолчанию и соответственно в программе должны быть вызовы такой функции в разной форме.
· Использовать все циклы С++.
· Доступ к элементам массива по [] и *.
· Заполнение массива случайным образом.
· Программа должна создаваться из проекта, содержащего несколько файлов исходного кода (*.h, *.срр).
· Должны использоваться уловная компиляция (стражи включения).
· Программа должна иметь дружественный интерфейс - основные операции должны вызываться через соответствующие элементы текстового меню.
· Итерации в текстовый файл отчета.
· Передача имени файла отчета в командной строке.
· Считывание исходных данных из файла.
· Использование параметров командной cтроки.
Теоретическое обоснование метода
и алгоритм решения задачи
Метод основывается на следующем: считается, что перед рассмотрением записи R[j] предыдущие записи R[1],R[2]. R[j-1] уже упорядочены, и R[j] вставляется в соответствующее место. Сортировка таблицы начинается со второй записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность нарушена, то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами записей R[2] и R[1]. Как только программа обнаруживает, что (j+1)-й элемент массива меньше (при сортировке по возрастанию) j-го элемента, она копирует значение этого элемента в буферную переменную и с начала массива до j анализирует, пока значение буферной переменной не будет меньше какого-либо элемента х. Затем кусок массива, начиная с х и до j, перемещается на одну ячейку в сторону возрастания, и на образовавшееся место х записывается значение перемещаемого элемента. Дальше продолжается перемещение по основному массиву до элемента n-1 (т.к. мы сравниваем j-й и (j+1)-й элементы):
Сортировка вставками (англ. Insertion sort) — квадратичный алгоритм сортировки.
Содержание
Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве [math]\displaystyle \frac
Алгоритм работает за [math]O(n + k)[/math] , где [math]k[/math] — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за [math]O(n^2)[/math] . Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.
Пример работы алгоритма для массива [math][ 5, 2, 4, 3, 1 ][/math]
Теперь вместо линейного поиска позиции мы будем использовать бинарный поиск, следовательно количество сравнений изменится с [math]O(N^2)[/math] до [math] O(N\log N) [/math] . Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.
Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее. Пример для набора элементов [math][ 5, 7, 3, 4, 6 ][/math]
Как можно заметить структура поля вывода имеет сходство с деком, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего [math]3[/math] элемента. Благодаря тому что для вставки [math]j[/math] -ого элемента потребуется [math]j/2[/math] сдвигов в худшем случае вместо [math]j[/math] , то и итоговое число необходимых операций в худшем случае составит [math]N^2 / 4 + N \log N[/math] .
Изучение алгоритмов и разновидности методов сортировки в программировании. Характеристика ее видов: сортировка пузырьком, перемешиванием, методом вставок, подсчётом, слиянием, цифровая, поразрядная, методом выбора, методом Шелла, пирамидальная и быстрая.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 20.11.2014 |
| Размер файла | 32,1 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное агентство железнодорожного транспорта
Алгоритмы сортировки. Сортировка вставками
1. Алгоритмы сортировки
2. Разновидности методов сортировки
2.1 Сортировка пузырьком
2.2 Сортировка перемешиванием
2.3 Сортировка методом вставок
2.4 Сортировка подсчётом
2.5 Сортировка слиянием
2.6 Цифровая сортировка
2.7 Поразрядная сортировка
2.8 Сортировка методом выбора
2.9 Сортировка методом Шелла
2.10 Пирамидальная сортировка
2.11 Быстрая сортировка
В наше время новые информационные технологии занимают очень важное место не только в специализированных, но и в повседневных сферах жизни. Компьютеры применяются в бизнесе, менеджменте, торговле, учебе и многих других сферах деятельности человека.
Компьютерные технологии очень удобны для выполнения разнообразных операций, но в разных сферах применения эти операции разные. Потому, каждая отдельная отрасль, которая использует специфические технические средства, нуждается в своих собственных программах, которые обеспечивают работу компьютеров.
Разработкой программного обеспечения занимается такая отрасль науки, как программирование. Она приобретает все большее и большее значение в последнее время, ведь с каждым днем компьютер становится все более необходимым, все более повседневным явлением нашей жизни. Ведь вычислительная техника прошлых лет уже почти полностью исчерпала себя и не удовлетворяет тем потребностям, которые появляются перед человечеством. алгоритм программирование сортировка цифровой
Таким образом, новые информационные технологии очень актуальны в наше время и нуждаются в большем внимании для последующей разработки и совершенствования. Рядом с этим, большое значение имеет также и программирование, которое является одним из фундаментальных разделов информатики и потому не может оставаться в стороне.
Программирование содержит целый ряд важных внутренних задач. Одной из наиболее важных задач для программирования является задача сортировки. Под сортировкой обычно понимают перестановки элементов любой последовательности в определенном порядке. Эта задача является одной из важнейших потому, что ее целью является облегчение последующей обработки определенных данных и, в первую очередь, задачи поиска. Одним из эффективных алгоритмов поиска является бинарный поиск. Он работает быстрее, чем, например, линейный поиск, но его возможно применять лишь при условии, что последовательность уже упорядочена, то есть отсортирована.
Вообще, известно, что в любой сфере деятельности, которая использует компьютер для записи, обработки и сохранения информации, все данные сохраняются в базах данных, которые также нуждаются в сортировке. Определенная упорядоченность для них очень важна, ведь пользователю намного легче работать с данными, которые имеют определенный порядок.
Задача сортировки в программировании не решена полностью. Ведь, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что одну и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности алгоритмов сортировки является, прежде всего, эффективность по времени и экономное использование памяти. Согласно этим требованиям, простые алгоритмы сортировки (такие, как сортировка выбором и сортировки включением) не являются очень эффективными.
Алгоритм сортировки обменами, хотя и завершает свою работу (поскольку он использует лишь циклы с параметром и в теле циклов параметры принудительно не изменяются) и не использует вспомогательной памяти, но занимает много времени. Даже, если внутренний цикл не содержит ни одной перестановки, то действия будут повторяться до тех пор, пока не завершится внешний цикл.
Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.
1. Алгоритмы сортировки
Алгоритм сортировки -- это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Оценка алгоритма сортировки. Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.
Время сортировки -- основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение -- это O(n log n) и плохое поведение -- это Щ(nІ). Идеальное поведение для сортировки -- O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в Щ(n log n) сравнениях в среднем;
Память -- ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) -- устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения -- эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим объём данных не позволяет им разместиться в ОЗУ
Список алгоритмов сортировки
В этой таблице n -- это количество записей, которые необходимо отсортировать, а k -- это количество уникальных ключей.
Алгоритмы устойчивой сортировки
Сортировка пузырьком (англ. Bubble sort ) -- сложность алгоритма: Q(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку
Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort, bidirectional bubble sort) -- Сложность алгоритма: O(n2)
Сортировка методом вставок (Insertion sort) -- Сложность алгоритма: O(n2); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда
Блочная сортировка (Корзинная сортировка, Bucket sort) -- Сложность алгоритма: O(n); требуется O(k) дополнительной памяти
Сортировка подсчетом (Counting sort) -- Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти
Сортировка слиянием (Merge sort) -- Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем -- сливаем отсортированные списки
In-place merge sort -- Сложность алгоритма: O(n2)
Двоичное древо сортировки (Binary tree sort) -- Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) -- Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
Поразрядная сортировка (Radix sort) -- Сложность алгоритма: O(n·k); требуется O(n) дополнительной памяти сортирует строки буква за буквой
Гномья сортировка (Gnome sort) -- Сложность алгоритма: O(n2)
Алгоритмы неустойчивой сортировки
Сортировка методом выбора (Selection sort) -- Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
Сортировка методом Шелла (Shell sort) -- Сложность алгоритма: O(n log n); попытка улучшить сортировку вставками
Сортировка расчёской (Comb sort) -- Сложность алгоритма: O(n log n)
Пирамидальная сортировка (Сортировка кучи, Heapsort) -- Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (Smoothsort) -- Сложность алгоритма: O(n log n)
Быстрая сортировка (Quicksort) -- Сложность алгоритма: O(n log n) -- среднее время, O(n2) -- худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort -- Сложность алгоритма: O(n log n)
Patience sorting -- Сложность алгоритма: O(n log n + k) -- наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
Непрактичные алгоритмы сортировки
Сортировка Акульшина (Akulshin sort) -- O(n Ч n!) -- худшее время. Генерируем всевозможные перестановки исходного массива и для каждой осуществдяем проверку верной отсортированности.
Глупая сортировка (Stupid sort) -- O(n3); рекурсивная версия требует дополнительно O(n2) памяти
Bead Sort -- O(n) or O(vn), требуется специализированное железо
Блинная сортировка (Pancake sorting) -- O(n), требуется специализированное железо
2. Разновидности методов сортировки
2.1 Сортировка пузырьком
Сортировка методом пузырька имеет сложность O(n2). Для понимания и реализации это -- простейший алгоритм сортировки, но эффективен он лишь для небольших массивов.
Пример реализации алгоритма (язык Pascal):
for i := n - 1 downto 1 do
for j := 1 to i do
if a[j] > a[j+1] then
2.2 Сортировка перемешиванием
Сортировка перемешиванием (шейкер-сортировка) -- разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие -- к началу.
Лучший случай для этой сортировки -- отсортированный массив (О(n)), худший -- отсортированный в обратном порядке (O(nІ)).
2.3 Сортировка методом вставок
Сортировка методом вставок (англ. insertion sort) -- простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:
прост в реализации
эффективен на небольших наборах данных
эффективен на наборах данных, которые уже частично отсортированы
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
может сортировать список по мере его получения
На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива -- произволен, может использоваться практически любой алгоритм выбора.
2.4 Сортировка подсчётом
Сортировка подсчётом -- алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.
2.5 Сортировка слиянием
Алгоритм был изобретён Джоном фон Нейманом в 1945 году.
Двоичное дерево (структура данных)
Двоичное дерево -- абстрактная структура данных, являющееся программной реализацией двоичного дерева (графа). Оно состоит из узлов (записей) вида (data, l, r), где data -- некоторые данные привязанные к узлу, l, r -- ссылки на узлы, являющиеся детьми данного узла. Узел l называется левым ребёнком, а узел r -- правым.
2.6 Цифровая сортировка
Алгоритм цифровой сортировки действует следующим образом:
Просматриваем изначальный массив, помещая каждый его элемент в свою ячейку.
Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.
Эффективность этого алгоритма сильно зависит от плотности элементов в массиве ячеек. Если элементов этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.
Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В особенности, блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).
2.7 Поразрядная сортировка
Поразрядная сортировка -- быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв.
2.8 Сортировка методом выбора
Сортировка методом выбора (англ. selection sort) -- алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае И(n2), предполагая, что сравнения делаются за постоянное время.
находим минимальное значение в текущем списке
производим обмен этого значения со значением на первой позиции
теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных ключа для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.
2.9 Сортировка методом Шелла
Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.
Анализ алгоритма сортировки Шелла
Время выполнения сортировки пропорционально n1.2. Эта зависимость значительно лучше квадратичной зависимости n2, которой подчиняется большинство простых алгоритмов сортировки.
Алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить их в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива (рис. 9).
Тогда при j = 0 будет заведомо верно a[0] = 0. Таким образом, сортировка будет происходить правильным образом, а во внутреннем цикле станет на одно сравнение меньше. С учетом того, что оно производилось О(n 2 ) раз, это - реальное преимущество. Однако отсортированный массив будет неполон, так как из него исчезло первое число. Для окончания сортировки это число следует вернуть назад, а затем вставить в отсортированную последовательность a[1]. a[n] (рис. 10). При использовании таких приращений среднее количество операций: O(n 7/6 ), в худшем случае - порядка O(n 4/3 ). Обратим внимание на то, что последовательность вычисляется в порядке, противоположном используемому: inc[0] = 1, inc[1] = 5, . Формула дает сначала меньшие числа, затем все большие и большие, в то время как расстояние между сортируемыми элементами, наоборот, должно уменьшаться. Поэтому массив приращений inc вычисляется перед запуском собственно сортировки до максимального расстояния между элементами, которое будет первым шагом в сортировке Шелла. Потом его значения используются в обратном порядке. При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size. Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size. Пирамидальная сортировка Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n). В качестве вступления к основному методу рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки наименьшего элемента в левый конец массива, будем выбирать наибольший элемент, а готовую последовательность строить в правом конце. Пример действий для массива a[0]. a[7]: 44 55 12 42 94 18 06 67 исходный массив 44 55 12 42 67 18 06 |94 94 67 44 55 12 42 06 18 |67 94 67 06 44 18 12 42 06 |55 67 94 55 18 06 18 12 42 |44 55 67 94 44 06 06 18 12 |42 44 55 67 94 42 42 06 12 |18 42 44 55 67 94 18 12 06 |12 18 42 44 55 67 94 12 12 Вертикальной чертой отмечена левая граница уже отсортированной (правой) части массива. Рассмотрим оценку количества операций подробнее. Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]..a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности, поэтому необходимое на него время: O(n). Итак, n шагов по O(n) каждый - это O(n 2 ). Произведем усовершенствование: построим структуру данных, позволяющую выбирать максимальный элемент последовательности не за O(n), а за O(log n) времени. Тогда общее быстродействие сортировки будет n*O(log n) = O(n log n). Эта структура также должна позволять быстро вставлять новые элементы (чтобы быстро ее построить из исходного массива) и удалять максимальный элемент (он будет помещаться в уже отсортированную часть массива - его правый конец). Итак, назовем пирамидой (Heap) бинарное дерево высоты k, в котором: · все узлы имеют глубину k или k-1, то есть дерево сбалансированное;
· при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид, как на рис. 16: · выполняется "свойство пирамиды": каждый элемент меньше, либо равен родителю (рис. 17).
Как хранить пирамиду? Наименее хлопотно - поместить ее в массив. Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме:
Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2]. Плюсы такого хранения пирамиды очевидны: · никаких дополнительных переменных, нужно лишь понимать схему; · узлы хранятся от вершины и далее вниз, уровень за уровнем; · узлы одного уровня хранятся в массиве слева направо. Запишем в виде массива пирамиду, изображенную выше. Слева направо, сверху вниз: 94 67 18 44 55 12 06 42. На рисунке 17 место элемента пирамиды в массиве обозначено цифрой справа вверху от него. Восстановить пирамиду из массива как геометрический объект легко - достаточно вспомнить схему хранения и нарисовать, начиная от корня. Шаг 1: построение пирамиды Начать построение пирамиды можно с a[k]. a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i, j: i = 2i+1 (или j = 2i+2 ), потому что такие i, j находятся за границей массива. Следует заметить, что a[k]. a[n] не является пирамидой как самостоятельный массив. Это, вообще говоря, неверно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]. a[n]. Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления - тот, который стоит перед уже готовой частью. Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]. a[n] на элемент a[i] влево: 1. Смотрим на сыновей слева и справа (в массиве это a[2i+1] и a[2i+2]) и выбираем наибольшего из них. 2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе процедура заканчивается. Новый элемент "просеивается" сквозь пирамиду. Учитывая, что высота пирамиды h = 0; i--) downHeap(a, i, size-1); Ниже дана иллюстрация процесса для пирамиды из 8 элементов: 44 55 12 42 // 94 18 06 67 Справа - часть массива, удовлетворяющая 44 55 12 // 67 94 18 06 42 свойству пирамиды, 44 55 // 18 67 94 12 06 42 остальные элементы добавляются 44 // 94 18 67 55 12 06 42 один за другим, справа налево. // 94 67 18 44 55 12 06 42 В геометрической интерпретации ключи из начального отрезка a[size/2]. a[n] являются листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так пока не будет построена вся пирамида. На рис. 18, 19 изображен процесс построения. Неготовая часть пирамиды (начало массива) окрашена в белый цвет, удовлетворяющий свойству пирамиды конец массива - заштрихован. Шаг 2: сортировка Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2: 1. Берем верхний элемент пирамиды a[0]. a[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив a[0]. a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент. 2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента (рис. 20). Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность. 94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки 67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды 55 42 44 06 12 18 // 67 94 44 42 18 06 12 // 55 67 94 42 12 18 06 // 44 55 67 94 18 12 06 // 42 44 55 67 94 12 06 // 18 42 44 55 67 94 06 // 12 18 42 44 55 67 94
Исходная картина, 94, 18, 06, 67 - листья Сравнили 42 и 67 и поменяли их местами 12 сравнили с max(18, 6) = 18 55 сравнили с max(67, 94) = 94
Рис. 19 Код внешней процедуры сортировки: Каково быстродействие получившегося алгоритма ? Построение пирамиды занимает O(n log n) операций, причем более точная оценка дает даже O(n) за счет того, что реальное время выполнения этой процедуры зависит от высоты уже созданной части пирамиды. Вторая фаза занимает O(n log n) времени: O(n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы. Пирамидальная сортировка не использует дополнительной памяти. Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом. Поведение неестественно: частичная упорядоченность массива никак не учитывается.
Обменяли 94 и 42, забыли о 94 Просеяли 42 сквозь 67, 55 Обменяли 06 и 67, забыли о 67 Просеяли 06 сквозь 55, 44 Быстрая сортировка Этот метод был разработан более 40 лет назад. Это наиболее широко применяемый и один из самых эффективных алгоритмов. Метод основан на подходе "разделяй-и-властвуй". Общая схема такова: 1) из массива выбирается некоторый опорный элемент a[i]; 2) запускается процедура разделения массива, которая перемещает все ключи, меньшие либо равные a[i], влево от него, а все ключи, большие либо равные a[i] - вправо, 3) теперь массив состоит из двух подмножеств, причем левое меньше либо равно правому (рис.21); 4) для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру. В конце получится полностью отсортированная последовательность. Далее алгоритм будет рассмотрен подробнее. Разделение массива На входе массив a[0]. a[N] и опорный элемент p, по которому будет производиться разделение. 1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности. 2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] void quickSortR(T* a, long N) >1 ]; // центральный элемент do < // процедура разделения while ( a[i] p ) j--; if (i 0 ) quickSortR(a, j); if ( N >i ) quickSortR(a+i, N-i);> Каждое разделение требует, очевидно, О(n) операций. Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике. Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n 2 ) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге. Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части. Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек. Модификации кода и метода Во-первых, из-за рекурсии и других "накладных расходов" Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%. Для проведения метода в жизнь можно модифицировать функцию quickSortR, заменив последние 2 строки на if ( j > CUTOFF ) quickSortR(a, j); if ( N > i + CUTOFF ) quickSortR(a+i, N-i); Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из void qsortR(T *a, long size) < quickSortR(a, size-1); insertSort(a, size); // insertSortGuarded быстрее, но нужна функция setmax()> Во-вторых, в случае явной рекурсии, как в программе выше, в стеке сохраняются не только границы подмассивов, но и ряд совершенно ненужных параметров, таких как локальные переменные. Если эмулировать стек программно, его размер можно уменьшить в несколько раз. В-третьих, чем на более равные части будет делиться массив, тем лучше. Потому в качестве опорного целесообразно брать средний из трех, а если массив достаточно велик - то из девяти произвольных элементов. В-четвертых, пусть входные последовательности очень плохи для алгоритма. Например, их специально подбирают, чтобы средний элемент оказывался каждый раз минимумом. Как сделать QuickSort устойчивой к такому "саботажу"? Очень просто - выбирать в качестве опорного случайный элемент входного массива. Тогда любые неприятные закономерности во входном потоке будут нейтрализованы. Другой вариант - переставить перед сортировкой элементы массива случайным образом. В-пятых, быструю сортировку можно использовать и для двусвязных списков. Единственная проблема при этом - отсутствие непосредственного доступа к случайному элементу. Так что в качестве опорного приходится выбирать первый элемент, и либо надеяться на хорошие исходные данные, либо случайным образом переставить элементы перед сортировкой. При использовании рекурсивного кода, подобного написанному выше, это будет означать n вложенных рекурсивных вызовов функции QuickSort. Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям. Для исключения подобной ситуации можно заменить рекурсию на итерации, реализовав стек на основе массива. Процедура разделения будет выполняться в виде цикла. Каждый раз, когда массив делится на две части, в стек будет направляться запрос на сортировку большей из них, а меньшая будет обрабатываться на следующей итерации. Запросы будут выбираться из стека по мере освобождения процедуры разделения от текущих задач. Сортировка заканчивает свою работу, когда запросы кончаются. Читайте также:
|
