Сортировки
В любой сфере деятельности, которая использует компьютер для записи, обработки и сохранения информации, все данные сохраняются в базах данных, которые также нуждаются в сортировке. Определенная упорядоченность для них очень важна, так как пользователю намного легче работать с данными, которые имеют определенный порядок.
Задача сортировки в программировании не решена полностью, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки.
Сортировка данных – один из этапов обработки данных, упорядочение элементарных данных в последовательности, определяемой значениями некоторых признаков, называемых ключами сортировки.
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Классы алгоритмов сортировки
Основные:- сортировка обменом (перестановками);
- сортировка выбором (отбором);
- сортировка вставкой.
- сортировка подсчетом;
- сортировка слиянием;
- распределяющая сортировка.
Оценка алгоритмов сортировки
- Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n ln n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей, всегда нуждаются по меньшей мере в O(n ln n) сравнениях в среднем.
- Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Классификация алгоритмов сортировки
- Устойчивость – устойчивая сортировка не меняет взаимного расположения равных элементов.
- Естественность поведения – эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
- Использование операции сравнения – алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n ln n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Классификация по сфере применения
- Внутренняя сортировка – оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке; данные обычно упорядочиваются на том же месте, без дополнительных затрат.
- Внешняя сортировка – оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов).
Алгоритмы устойчивой сортировки
- Сортировка пузырьком – Сложность алгоритма: O(n^2); для каждой пары индексов производится обмен, если элементы расположены не по порядку.
- Сортировка перемешиванием – Сложность алгоритма: O(n^2).
- Сортировка вставками – Сложность алгоритма: O(n^2); определяем, где текущий элемент должен находится в упорядоченном списке, вставляем его туда.
- Блочная сортировка – Сложность алгоритма: O(n); требуется O(k) дополнительной памяти.
- Сортировка подсчётом – Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти.
- Сортировка слиянием – Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки.
- Двоичное дерево сортировки – Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти.
- Цифровая сортировка – Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти.
- Гномья сортировка – Сложность алгоритма: O(n^2).
Алгоритмы неустойчивой сортировки
- Сортировка выбором – Сложность алгоритма: O(n^2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка.
- Сортировка Шелла – Сложность алгоритма: O(n log^2 n); попытка улучшить сортировку вставками.
- Сортировка расчёской – Сложность алгоритма: O(n log n).
- Пирамидальная сортировка – Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка.
- Плавная сортировка – Сложность алгоритма: O(n log n).
- Быстрая сортировка – Сложность алгоритма: O(n log n) – среднее время, O(n^2) – худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине.
- Обменная поразрядная сортировка – Сложность алгоритма: O(n*k); требуется O(k) дополнительной памяти.
Непрактичные алгоритмы сортировки
- Сортировка перестановкой – Сложность алгоритма: O(n*n!); генерируются всевозможные перестановки исходного массива и для каждой осуществляется проверка верного порядка.
- Глупая сортировка – Сложность алгоритма: O(n^3); рекурсивная версия требует дополнительно O(n^2) памяти
- Блинная сортировка – Сложность алгоритма: O(n); требуется специализированное аппаратное обеспечение.
Алгоритмы, не основанные на сравнениях
- Блочная сортировка.
- Лексикографическая или поразрядная сортировка.
- Сортировка подсчётом.
Остальные алгоритмы сортировки
- Топологическая сортировка.
- Внешняя сортировка.
| Сложность | Наилучший случай | В среднем | Наихудший случай |
|---|---|---|---|
| Время | O(n) | O(n ^ 2) | O(n ^ 2) |
| Память | O(1) | O(1) | O(1) |
Сортировка пузырьком – это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива.
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов.
роходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде – отсюда и название алгоритма).
Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент находится на N-1 месте. И так далее.
| Сложность | Наилучший случай | В среднем | Наихудший случай |
|---|---|---|---|
| Время | O(n) | O(n ^ 2) | O(n ^ 2) |
| Память | O(1) | O(1) | O(1) |
Сортировка выбором — это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
Шаги алгоритма:- находим номер минимального значения в текущем списке;
- производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.
Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.
| Сложность | Наилучший случай | В среднем | Наихудший случай |
|---|---|---|---|
| Время | O(n) | O(n ^ 2) | O(n ^ 2) |
| Память | O(1) | O(1) | O(1) |
Сортировка вставками – простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы, у него есть ряд преимуществ:
- прост в реализации;
- эффективен на небольших наборах данных;
- эффективен на наборах данных, которые уже частично отсортированы;
- это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
- может сортировать список по мере его получения.
На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива, произволен; может использоваться практически любой алгоритм выбора.
| Сложность | Наилучший случай | В среднем | Наихудший случай |
|---|---|---|---|
| Время | O(n * log n) | O(n * log n) | O(n * log n) |
| Память | O(n) | O(n) | O(n) |
Разделяй и властвуй
Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще.
Мы пользуемся ими каждый день.
К примеру, поиск в телефонной книге — один из примеров такого алгоритма. Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много — до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную.
При сортировке слиянием разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.
Достоинства и недостатки
Достоинства:- работает даже на структурах данных последовательного доступа;
- хорошо сочетается с подкачкой и кэшированием памяти;
- неплохо работает в параллельном варианте: легко разбить задачи между процессорами поровну, но трудно сделать так, чтобы другие процессоры взяли на себя работу, в случае если один процессор задержится;
- не имеет «трудных» входных данных;
- устойчивая – сохраняет порядок равных элементов.
- на «почти отсортированных» массивах работает столь же долго, как на хаотичных;
- требует дополнительной памяти по размеру исходного массива.
| Сложность | Наилучший случай | В среднем | Наихудший случай |
|---|---|---|---|
| Время | O(n * log n) | O(n * log n) | O(n ^ 2) |
| Память | O(1) | O(1) | O(1) |
Быстрая сортировка, сортировка Хоара – широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Быстрая сортировка — это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:
- выбрать элемент из массива (опорный);
- разбиение: перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные после;
- рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
Для выбора опорного элемента и операции разбиения существуют разные подходы, влияющие на производительность алгоритма.
Выбор опорного элемента
В ранних реализациях, как правило, опорным выбирался первый элемент, что снижало производительности на отсортированных массивах. Для улучшения эффективности может выбираться средний, случайный элемент или (для больших массивов) медиана первого, среднего и последнего элементов. Медиана всей последовательности является оптимальным опорным элементом, но её вычисление слишком трудоёмко для использования в сортировке.
Достоинства и недостатки
Достоинства:- один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения;
- алгоритм очень короткий: запомнив основные моменты, его легко написать «из головы», невелика константа при n log n;
- требует лишь O(log n) дополнительной памяти для своей работы (не улучшенный рекурсивный алгоритм в худшем случае O(n) памяти);
- хорошо сочетается с механизмами кэширования и виртуальной памяти;
- допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах);
- допускает эффективную модификацию для сортировки по нескольким ключам благодаря тому, что в процессе разделения автоматически выделяется отрезок элементов, равных опорному, этот отрезок можно сразу же сортировать по следующему ключу;
- работает на связных списках и других структурах с последовательным доступом, допускающих эффективный проход как от начала к концу, так и от конца к началу
- сильно деградирует по скорости (до O(n ^ 2)) в худшем или близком к нему случае, что может случиться при неудачных входных данных;
- прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека, так как в худшем случае ей может потребоваться сделать O(n) вложенных рекурсивных вызовов;
- неустойчив.
Реализация сортировки пузырьком на псевдокоде:
Реализация сортировки пузырьком на C:
Примечание
Все приведённые реализации алгоритма имеют недостаток: каждый раз во внешнем цикле длина проходимого участка уменьшается на единицу, в то время как следующий проход должен идти до места последнего обмена.
Источник: Сортировка пузырьком — Википедия
Реализация сортировки выбором на C++:
Реализация сортировки выбором на C#:
Источник: Сортировка выбором — Википедия
Псевдокод
На вход процедуре сортировки подаётся массив A[1..n], состоящий из элементов последовательности A[1], A[2], ..., A[n], которые требуется отсортировать. n соответствует A.length — размеру исходного массива. Для сортировки не требуется привлечения дополнительной памяти, кроме постоянной величины для одного элемента, так как выполняется перестановка в пределах массива. В результате работы процедуры во входном массиве оказывается требуемая выходная последовательность элементов.
Реализация сортировки вставкой на псевдокоде:
Источник: Сортировка вставкой — Википедия
Реализация сортировки слиянием на псевдокоде:
Реализация сортировки слиянием на языке программирования Python:
Реализация сортировки слиянием на языке программирования Pascal:
Реализация сортировки слиянием на языке программирования C:
Реализация сортировки слиянием на языке программирования C++ 11:
Источник реализации на псевдокоде, C, C++: Сортировка слиянием — Википедия
Реализация быстрой сортировки на языке программирования Python:
Реализация быстрой сортировки на языке программирования Pascal:
Реализация быстрой сортировки на языке программирования C#:
Найти в Интернете
Самоконтроль
Информационные технологии сегодня играют исключительно важную роль в обеспечении информационного взаимодействия между людьми, а также в системах подготовки и распространения массовой информации. Поэтому очень важно заниматься саморазвитием, составной частью которого является самоконтроль.
Тестовые задания для контроля знаний по классификациям алгоритмов сортировки:
- Классы алгоритмов сортировки
- Оценки алгоритмов сортировки
- Классификация алгоритмов сортировки
- Классификация алгоритмов по сфере применения
Тестовые задания для контроля знаний алгоритмов сортировки:
О приложении
Сортировку следует понимать, как процесс перегруппировки заданного множества объектов в некотором определенном порядке.
Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве.
Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики.
Приложение LearnSort разработано с целью саморазвития и углубленного изучения алгоритмов сортировки.
Приложение рассчитано на широкий круг пользователей, заинтересованных в изучении и систематизации своих знаний в области методов внутренней сортировки. В приложении систематизирована и сгруппирована информация по пяти методам внутренней сортировки: сортировка пузырьком, сортировка выбором, сортировка, вставками, сортировка слиянием и быстрая сортировка.
Приложение может использоваться на уроках информатики в школе, факультативных занятиях, а также для профессиональной подготовки специалистов в области информационных технологий, изучая материал от простого к сложному.
Приложение имеет блочную структуру и состоит из модулей: О приложении, Сортировки, Алгоритмы сортировки, Реализация, Визуализация, Самоконтроль и О разработчиках.
Модуль Сортировки содержит информацию о сортировке, их классах, алгоритмах сортировки, их классификации.
Модуль Алгоритмы сортировки состоит из пяти вкладок по сортировкам: сортировка пузырьком, сортировка выбором, сортировка, вставками, сортировка слиянием и быстрая сортировка, которые имеют однотипную структуру. Каждая вкладка состоит из описания метода сортировки, алгоритма и видеоматериала (создан в университете Сапиентия, Тыргу-Муреш (Marosvásárhely), Румыния).
Модуль Реализация содержит реализацию алогритмов сортировки на учебном языке программирования Паскаль и в других средах разработки.
В модуле Визуализация приведены примеры программной реализации методов внутренней сортировки, с возможностью изменения размера массива, инициализации массива, наличием или отсутствием отрицательных чисел, интервале визуальной задержки отображения графической информации, а для быстрой сортировки имеется возможность выбора опорного элемента сортировки.
Модуль Самоконтроль содержит on-line тесты разработанные и опубликованные в приложении learningapps.org. Одна из главных задач воспитания подрастающего поколения – это формирование самостоятельности мышления, подготовка к творческой деятельности, это требование времени, это социальная задача.
Приложение разработано с использованием языка гипертекстовой разметки HTML, каскадных таблиц стилей CSS, языка программирования JavaScript. Для эстетического оформления использован фреймворк Bootstrap, для удобного взаимодействия с DOM – библиотека jQuery, для визуализации алгоритмов сортировок – скрипт sorting.js (https://github.com/jcjohnson/sorting.js) от профессора Стэнфордского университета.
Скрипт sorting.js, библиотека jQuery для удобного взаимодействия с DOM и фреймворк Bootstrap выпущены под лицензией MIT, разрешающей использовать её как в коммерческих, так и в обучающих целях (https://ru.wikipedia.org/wiki/Лицензия_MIT).
Для наполнения приложения учебным материалом использовались учебные пособия по языкам программирования, информационным технологиям, словари и личный опыт преподавателя.
О разработчиках
Платонова Тамара Юрьевна
Руководитель
Место работы: Учреждения образования «Новопольский государственный аграрно-экономический колледж», преподаватель 1-ой категории.
Семёнов Илья Сергеевич
Разработчик приложения LearnSort
Место учёбы: Учреждения образования «Новопольский государственный аграрно-экономический колледж», учащийся 4-го курса специальности 2-40 01 01 «Программное обеспечение информационных технологий».