Автор Анна Евкова
Преподаватель который помогает студентам и школьникам в учёбе.

Алгоритмы сортировки данных(Понятие алгоритма и сортировки)

Содержание:

ВВЕДЕНИЕ

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

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

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

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

Задача сортировки в программировании не решена полностью. Ведь, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что одну и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности алгоритмов сортировки является, прежде всего, эффективность по времени и экономное использование памяти.

Задачами курсовой работы являются:

  1. Найти определение понятию алгоритма сортировки;
  2. Определить основные параметры оценки алгоритмов сортировки;
  3. Рассмотреть различные методы сортировки данных;

Весь представленный исходный код сортировок написан на языке программирования Java.

Глава 1. Понятие алгоритма и сортировки

Понятие алгоритма является центральным понятием информатики. Слово «алгоритм» произошло от имени узбекского математика аль-Хорезми, который еще в IX веке сформулировал правила выполнения арифметических действий. В современной математике и информатике термин алгоритм имеет следующие определения:

— последовательность действий со строго определенными правилами выполнения;

— предписание, определяющее содержание и последовательность операций, переводящих исходные данные в искомый результат;

— точное описание некоторого вычислительного процесса или любой иной последовательности действий;

— точное и полное предписание о последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.

Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством — формальным исполнителем. Задача исполнителя — точная реализация уже имеющегося алгоритма. Формальный исполнитель не обязан вникать в сущность алгоритма, а возможно, и неспособен его понять.

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

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Глава 2. Оценка сложности алгоритма

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n. Тогда говорят, что временная сложность этого алгоритма равна О(n3), т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).

Примеры:

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n2) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n2.

Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1). Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

Глава 3. Сортировка пузырьком

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

При определенных обстоятельствах сортировка пузырьком может быть достаточно быстрой, но это только в некоторых случаях. Как правило, данный вид сортировки служит только для учебных целей.

Сортировка пузырьком заключается в следующем:

Начиная с начала массива просматриваем попарно по 2 элемента (первый со вторым, второй с третий, третий с четвертым и т.д.). Если второй элемент в паре меньше первого элемента – перемещаем его на место первого, а первый на место второго. Это мы делаем для всех элементов. После того, как мы дошли до конца массива (сравнили предпоследний и последний элементы и сделали обмен, если нужно), проверяем, был ли хотя бы один обмен. Если да, значит массив не отсортирован и начинаем все сначала. Повторяем такие проходы, пока не будет так, что мы проверили попарно все элементы от начала до конца, а обмена ни одного не было. Таким образом элементы с самыми маленькими значениями потихоньку перемещаются справа налево. То есть они как будто всплывают, как мыльный пузырь. Отсюда и название метода – пузырьком.

Рисунок 1. Сортировка пузырьком

Вывод: 1 2 3 4 5 6 7 8 9 10

Глава 4. Сортировка выбором

Сортировка выбором – возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

Берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1. Находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key. Если номер первого элемента и номер найденного элемента не совпадают, т. е. если key≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит. Увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию. С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

Рисунок 2. Сортировка выбором

Вывод: 1 2 3 4 5 6 7 8 9 10

Глава 5. Сортировка вставкой

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

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

  1. первая и вторая карта меньше третьей;
  2. первая и вторая карта больше третьей;
  3. первая карта уступает значением третьей, а вторая превосходит ее;
  4. первая карта превосходит значением третью карту, а вторая уступает ей.

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

Рисунок 3. Сортировка вставкой для чисел

Вывод: 1 2 3 4 5 6 7 8 9 10

Рисунок 4. Сортировка вставкой для строк

Вывод: Com, Dot, Http, Java, Top, Tutorial

Глава 6. Пирамидальная сортировка

Алгоритм пирамидальной сортировки просто использует уже описанные алгоритмы для работы с пирамидами. Идея состоит в том, чтобы создать приоритетную очередь и последовательно удалять по одному элементу из очереди.

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

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

Рисунок 5. Пирамидальная сортировка

Вывод: 2 12 15 16 23 27 34 45 53 56 78 91

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

Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.

В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино.

Несколько детально этот процесс можно расписать так:

  1. Массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
  2. Далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
  3. В конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

Рисунок 6. Сортировка слиянием

Вывод: 1 2 3 4 5 6 7 8 9 10

Глава 8. Быстрая сортировка

Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(nlog n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

Общая идея алгоритма состоит в следующем:

  1. Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
  2. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».

3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Рисунок 7. Быстрая сортировка

Вывод: 1 2 3 4 5 6 7 8 9 10

Глава 9. Сортировка Шелла

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

Рисунок 8. Сортировка Шелла

Вывод: 1 2 3 4 5 6 7 8 9 10

Глава 10. Сортировка подсчётом

Алгоритм сортировки подсчётом (counting sort) применим, если каждый из n элементов сортируемой последовательности – целое положительное число в известном диапазоне (не превосходящее заранее известного k). Если k = О(n), то алгоритм сортировки подсчётом работает за время О(n).

Идея этого алгоритма заключается в том, чтобы для каждого элемента х предварительно подсчитать, сколько элементов входной последовательности меньше х. Далее х записывается напрямую в выходной массив в соответствии с этим числом (если, скажем, 5 элементов входного массива меньше х, то в выходном массиве х дол­жен быть записан на место номер 6). Если предположить, что в сортируемой последовательности могут присутствовать равные числа, то представленная схема потребует небольшой модификации, позволяющей избежать записи нескольких чисел на одно место.

Рисунок 9. Сортировка подсчётом

Вывод: 1 2 3 4 5 6 7 8 9 10

Глава 11. Поразрядная сортировка

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения. Например, так сортировать можно не только числа, записанные в виде набора цифр, но и строки, являющиеся набором символов, и вообще произвольные значения в памяти, представленные в виде набора байт.

Сравнение производится поразрядно: сначала сравниваются значения одного крайнего разряда, и элементы группируются по результатам этого сравнения, затем сравниваются значения следующего разряда, соседнего, и элементы либо упорядочиваются по результатам сравнения значений этого разряда внутри образованных на предыдущем проходе групп, либо переупорядочиваются в целом, но сохраняя относительный порядок, достигнутый при предыдущей сортировке. Затем аналогично делается для следующего разряда, и так до конца.

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц, least significant digit, LSD) или более значащих цифр (по левой стороне, со стороны более значащих разрядов, most significant digit, MSD).

При LSD сортировке (сортировке с выравниванием по младшему разряду, направо, к единицам) получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. То есть, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя отсортированность по единицам внутри десятков, затем по сотням, сохраняя отсортированность по десяткам и единицам внутри сотен, и т. п.

При MSD сортировке (с выравниванием в сторону старшего разряда, налево), получается алфавитный порядок, который уместен для сортировки строк текста. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам, приведённым в примере получим последовательность 2, 3, 23, 24, 44, 45, 66, 75, 90, 170, 232, 234, 802.

Рисунок 10. Сортировка подсчётом

Глава 12. Блочная сортировка

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

Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(n) (на удачных входных данных).

Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк значительно превосходит блочную сортировку скоростью.

Рисунок 10. Блочная сортировка

ЗАКЛЮЧЕНИЕ

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

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

Какой алгоритм, из множества известных сейчас самый быстрый?

Ответа на этот вопрос не существует. Нет самого оптимального алгоритма в абстрактном смысле. Выбор его очень сильно зависит от условия задачи, которую необходимо решить.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

  1. https://ru.wikipedia.org/ - Википедия
  2. https://webexsite.wordpress.com – блог Александра Богомолова
  3. https://habr.com/ - Хабр
  4. https://tproger.ru/ - сайт о программировании
  5. http://algolist.manual.ru – алгоритмы, методы, исходники
  6. https://neerc.ifmo.ru – университет ИТМО