Добавлен: 18.06.2023
Просмотров: 77
Скачиваний: 3
Введение
В век информационных технологий очень важное место в нашей жизни занимают компьютеры. Компьютеры применяются в бизнесе, менеджменте, торговле, учебе и многих других сферах деятельности человека.
Программисты, сетевые инженеры, системные администраторы, все они борются за то чтобы мы могли легко пользоваться программным обеспечением и чтобы компьютеры решали как можно больше рутинных задач, а так-же помогали нам в повседневной жизни, чтобы у людей оставалось больше времени на свои дела.
Программирование содержит целый ряд важных внутренних задач. Одной из наиболее важных задач для программирования является задача сортировки. Под сортировкой обычно понимают перестановки элементов любой последовательности в определенном порядке. Эта задача является одной из важнейших потому, что ее целью является облегчение последующей обработки определенных данных и, в первую очередь, задачи поиска. Одним из эффективных алгоритмов поиска является бинарный поиск. Он работает быстрее, чем, например, линейный поиск, но его возможно применять лишь при условии, что последовательность уже упорядочена, то есть отсортирована.
Вообще, известно, что в любой сфере деятельности, которая использует компьютер для записи, обработки и сохранения информации, все данные сохраняются в базах данных, которые также нуждаются в сортировке. Определенная упорядоченность для них очень важна, ведь пользователю намного легче работать с данными, которые имеют определенный порядок.
Так-же чтение с диска в последовательном порядке гораздо быстрее случайного порядка, благодаря сортировкам мы так-же увеличиваем производительность работы программного обеспечения .
Задача сортировки в программировании не решена полностью. Ведь, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что одну и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности алгоритмов сортировки является, прежде всего, эффективность по времени и экономное использование памяти. Согласно этим требованиям, простые алгоритмы сортировки (такие, как сортировка выбором и сортировки включением) не являются очень эффективными.
Алгоритм сортировки обменами, хотя и завершает свою работу (поскольку он использует лишь циклы с параметром и в теле циклов параметры принудительно не изменяются) и не использует вспомогательной памяти, но занимает много времени. Даже, если внутренний цикл не содержит ни одной перестановки, то действия будут повторяться до тех пор, пока не завершится внешний цикл.
Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.
Так-же по алгоритмам сортировки проводятся чемпионаты один из самых престижных и знаменитых Sort Benchmark известном как «Чемпионат мира» в области сортировки данных. В 2014 году Samsung заняла там первое место и поставили рекорд по скорости сортировки их Система сортировки называется DeepSort. Система от Samsung смогла проанализировать и реорганизовать 3,7 TБ данных за 60 секунд
Сортировка данных – это очень важный и сложный процесс во время разработки программного обеспечения, необходимо выбрать алгоритм, протестировать, и понять что это именно то что нужно для сортировки
Целью теоретической части курсовой работы является ознакомление с алгоритмами сортировки, попытка проанализировать их и осветить каждый из них.
Алгоритмы сортировки
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.
Оценка алгоритма сортировки
Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.
Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это ?(n?). Идеальное поведение для сортировки — O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в ?(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Список алгоритмов сортировки
В этой таблице n — это количество записей, которые необходимо отсортировать, а k — это количество уникальных ключей.
Алгоритмы устойчивой сортировки
Сортировка пузырьком (англ. Bubble sort ) —данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2). (Очень легкий в понимании чаще всего используется для обучения учеников алгоритмам сортировки и программированию)
Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort, bidirectional bubble sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Сортировка методом вставок (Insertion sort) — алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).
Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти. Алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Сортировка подсчетом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти. алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать.
Сортировка слиянием (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) — идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n).
Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n) разновидность пирамидальной сортировки
Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort — Сложность алгоритма: O(n log n) . Алгоритм использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов).