Что означает естественность поведения алгоритма
Понятия сортировки. Оценка алгоритмов сортировки. Классификация алгоритмов сортировки.
Основные понятия:
Сортировка является одной из фундаментальных алгоритмических задач программирования. Решением проблем, связанных с упорядочиванием элементов некоторого множества посвящено большое количество исследований и определен спектр алгоритмов.
Сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке с целью облегчить последующий поиск заданного элемента в данном множестве, причем под сортируемыми элементами могут пониматься произвольные объекты от чисел и символов до математических формул. В любом случае, сортировку можно представить следующим образом:
— Дан ряд элементов (A1, A2, …, An). Необходимо осуществить их перестановку в порядке (Ak1, Ak2, … Akn) так, чтобы элементы подчинялись функции упорядочивания F(Ak1) простые и улучшенные. Простые и улучшенные методы отличаются своей эффективностью. Специальные методы предназначены для сортировки информации определенной структуры.
Простые методы сортировки массивов.
К простым методам сортировки массивов относятся:
Сортировка пузырьком.
Сортировка пузырьком – наиболее простейший для реализации и понимания алгоритм сортировки, но эффективен он лишь для небольших массивов. Сложность алгоритма – n^2.
Данный алгоритм считается учебным и практически не применяется вне учебной литературы; вместо него на практике применяются более эффективные алгоритмы сортировки. В тоже время этот алгоритм лежит в основе некоторых более совершенных алгоритмов, таких как пирамидальная сортировка и быстрая сортировка.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Сортировка пузырьком не меняет взаимного расположения равных элементов и не использует дополнительной памяти.
Достоинства:
—Алгоритм является естественным и устойчивым.
Недостатки:
— Высокая вычислительная сложность алгоритма.
Сортировка выбором.
Сортировка выбором – один из классических методов упорядочивания последовательности, основывающийся на операции сравнения.
Может быть как устойчивым, так и неустойчивым.
Алгоритм:
— Находится минимальный (максимальный) элемент последовательности. Для этого первый элемент сравнивается со вторым, первый с третьим и т.д. Номер найденного элемента помечается.
— Если индекс первого элемента не тождественен этому элементу, то они обмениваются значениями.
— Сортировка продолжается на отсортированной части массива.
Число сравнений: N^2
Достоинства:
— Этому методу сортировки отдается предпочтение в тех случаях, когда записи файла огромны, а ключи занимают незначительное пространство.
— Данный алгоритм производит наиболее меньшее количество перемещений данных, нежели метод выбора.
Недостатки:
— Процесс нахождения минимального элемента за один проход не дает сведений о том, где будет находиться следующий минимальный элемент.
— На больших объемах данных данная сортировка является неэффективной.
Сортировка вставками.
Данный алгоритм выстраивает результирующий массив по одному элементу за раз. Он намного менее эффективен на больших списках, чем улучшенные методы сортировки (qsort/hsort). Однако, у данного алгоритма есть следующие достоинства:
— Эффективен на небольших наборах данных
— Наилучший случай – O(n)
— Требует только O(1) дополнительной памяти
Недостатки – высокая вычислительная сложность O(n^2).
Алгоритм:
На каждом шаге выбирается один из элементов входных данных и вставляется на нужную позицию в уже отсортированном списке до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно элементы вставляются по порядку их появления во входном массиве.
Сортировка слиянием.
Сортировка слиянием – алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к которым можно получать только последовательно) в определенном порядке. Сначала задача разбивается на подзадачи меньшего размера, затем они решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. После этого их решения комбинируются, и получается решение исходной задачи. Используется для внешней сортировки.
Наихудший случай – O(n log(n)).
Алгоритм:
Сортируемый массив разбивается на 2 массива примерно одинакового размера. Каждая из получившихся частей делится тем же самым алгоритмом до того, пока длина каждой части не будет равна 1; затем эти части массива соединяются в один и сортируются.
Достоинства:
— Сортировка является устойчивой.
— Эффективна при обработке данных с большим временем доступа.
— Наилучший способ сортировки связанных списков.
— Алгоритм удобен для структур с последовательным доступом к элементам.
Недостатки:
— Требует дополнительное пространство (O(1)).
— Уступает по быстродействию быстрой сортировке.
Курсовая работа: Алгоритмы сортировки
Тема: Алгоритмы сортировки
Тип: Курсовая работа | Размер: 219.62K | Скачано: 261 | Добавлен 23.04.11 в 08:48 | Рейтинг: +1 | Еще Курсовые работы
Год и город: Липецк 2011
Оглавление
2. Классификация элементов алгоритма сортировки………………….5
3. Характеристика методов сортировки………………………………..9
Практическая часть (вариант № 7) 20
4. Общая характеристика задачи………………………………………..20
5. Описание алгоритма решения задачи………………………………..22
Список литературы …27
Введение
Разработкой программного обеспечения занимается такая отрасль науки, как программирование. Программирование содержит целый ряд важных внутренних задач. Одной из наиболее важных задач для программирования является задача сортировки. Под сортировкой обычно понимают перестановки элементов любой последовательности в определенном порядке. Эта задача является одной из важнейших потому, что ее целью является облегчение последующей обработки определенных данных и, в первую очередь, задачи поиска.
Данная курсовая работа состоит из двух частей: теоретической и практической.
Целью теоретической части курсовой работы является ознакомление с алгоритмами сортировки, классификация алгоритмов и их подробная характеристика.
В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи: создание таблиц и заполнение таблиц данными; применение математических формул для выполнения запросов в ППП; построение графиков.
Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления курсовой работы:
Теоретическая часть
Алгоритм – это точно определенная последовательность действий, которую необходимо выполнить над исходными данными для достижения решения задачи.
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно разбить на три части:
Целью алгоритмов сортировки является упорядочение последовательности элементов данных.
2. Классификация элементов алгоритма сортировки
Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность.
Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Формы представления алгоритма:
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.
Виды алгоритмических структур:
1. Линейный алгоритм, в котором все команды выполняются последовательно одна за другой.
2. Разветвляющийся алгоритм, в котором в зависимости от условия выполнения либо одна серия команд, либо другая.
3. Циклический алгоритм, в котором многократно повторяется некоторый участок алгоритма.
Имеется два вида алгоритмов сортировки: сортировка массивов и сортировка последовательных файлов.
Сортировка массивов может находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах. Сортировка массива данных занимает одну из самых высоких проблем современных организаций. Ведь в каждой организации есть свои Базы данных на сотрудников, которых нужно отсортировывать, допустим, по Фамилии или по заработной плате по возрастанию или убыванию.
Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.
Классификация параметров оценки алгоритмов:
Память. Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость. Устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Объём данных не позволяет им разместиться в ОЗУ (оперативно запоминающие устройство).
Также алгоритмы классифицируются по:
Существует множество методов сортировки, каждый из которых имеет свои достоинства и недостатки. Рассмотрим лишь некоторые из них:
3. Характеристика методов сортировки
Наиболее известной (и наиболее «бесславной») является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма. Так как каждый раз на свое место становится, по крайней мере, один элемент, то не потребуется более N проходов, где N — количество элементов.
Схема 1. Алгоритм сортировки методом «пузырька»
Представляет собой разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие к началу.
Сортировка методом вставок (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ: прост в реализации; эффективен на небольших наборах данных; эффективен на наборах данных, которые уже частично отсортированы; это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы); может сортировать список по мере его получения.
На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.
Схема 2. Алгоритм сортировки методом вставок
Алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы. Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Алгоритм был изобретён Джоном фон Нейманом в 1945 году.
Цифровая сортировка (англ. pigeonhole sort) обладает линейной вычислительной сложностью (О(n)), что является лучшей возможной производительностью для алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить) в диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве устойчивой).
Алгоритм цифровой сортировки действует следующим образом:
Эффективность этого алгоритма сильно зависит от плотности элементов в массиве ячеек. Если элементов этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными. Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).
Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов.
Этот метод работает очень хорошо для небольших файлов. Его «внутренний цикл» состоит из сравнения a[i]min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить.
Кроме того, хотя сортировка выбором является методом «грубой силы», он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами.
Схема 3. Алгоритм сортировки методом выбора
Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.
Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке.
Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.
Схема 4. Алгоритм сортировки методом Шелла
Этот метод, совершенно отличен от всех схем сортировки, которые рассматривались прежде; в нем используется двоичное представление ключей, и потому он предназначен исключительно для двоичных машин. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли 0 или 1 отдельные биты ключа. В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструю сортировку. Так как он зависит от разрядов ключа, представленного в двоичной системе счисления, мы называем его «обменной поразрядной сортировкой». В общих чертах этот алгоритм можно описать следующим образом:
Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (т.е. гарантированно) за О(n log n) операций при сортировке n элементов.
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево – это такое двоичное дерево, у которого выполнены условия:
Алгоритм сортировки будет состоять из двух основных шагов:
1. Выстраиваем элементы массива в виде сортирующего дерева. Этот шаг требует О(n) операций.
Этот шаг требует О(n log n) операций.
Это самый быстрый метод сортировки, однако, существует множество существенных недостатков.
где A – это исходная последовательность (массив), Max(A) и Min(A) максимальный и минимальный элемент A,B – это вспомогательный массив, а Size(B) – это его размер. Эта монотонная (почти линейная) функция гарантирует, что ее значение на элементах сортируемого массива будут лежать в диапазоне от 1 до Size(B). Она определена только при Max(A) ≠ Min(A). Если же Max(A) = Min(B), то это означает, что массив состоит из одинаковых элементов, то есть он отсортирован.
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n 2 ) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций «сравнить» и «поменять местами», достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.
Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).
Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента.
Заключение
Решая конкретную экономическую задачу, необходимо выбрать множество данных, представляющих реальную ситуацию. Затем надлежит выбрать способ представления этой информации. Однако очень важную роль играют и свойства самих данных, операций, которые должны выполняться над ними. Современные средства программирования позволяют оперировать с множествами, массивами, записями, файлами (очередями).
Можно сделать вывод, что не существует одного единственного самого оптимального алгоритма сортировки. Найти оптимальный алгоритм, не привязываясь при его выборе к условию задачи невозможно.
Какой алгоритм, из множества известных сейчас самый быстрый?
Ответа на этот вопрос не существует. Нет самого оптимального алгоритма в абстрактном смысле. Выбор его очень сильно зависит от условия задачи, которую необходимо решить.
Практическая часть (вариант № 7)
4. Общая характеристика задачи
Постановка задачи:
Используя ППП (пакет прикладных программ) необходимо подвести итоги о результатах расчета стоимости по полученному заказу за октябрь 2006 года фирмы ООО «Стройдизайн» по каждому виду работ.
Текст задачи:
Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполнение работы приведен на рис. 7.1. Данные о заказанных работах указаны на рис. 7.2.