Алгоритмы сортировки информации в массивах — это алгоритмы, которые могут взять некую последовательность, составленную из компонентов массива, и переставить компоненты таким образом, чтобы сформированная последовательность удовлетворяла требуемым условиям.
Введение
Сортировка считается одной из базовых алгоритмических задач программирования. Решению проблем, которые связаны с сортировкой, посвящается большое количество научных исследований, спроектировано очень много алгоритмов. В общем случае сортировкой является процесс перегруппирования определённого множества объектов в необходимом порядке. Сортировка используется практически во всех сферах программирования, будь то базы данных или математические программы.
Алгоритмом сортировки является алгоритм, предназначенный для упорядочения определённого множества компонентов. Как правило, под алгоритмом сортировки подразумевается алгоритм, который выполняет упорядочивание множества компонентов по возрастанию или убыванию. При наличии компонентов, имеющих одинаковые значениям, в упорядоченной последовательности они должны располагаться рядом друг за другом в любом порядке. Тем не менее, часто считается полезным сохранять изначальный порядок следования компонентов, имеющих одинаковые значениям.
В алгоритмах сортировки только часть данных применяется как ключ сортировки. Ключом сортировки является атрибут, или набор атрибутов, по значению которого назначается порядок компонентов. Это означает, при формировании алгоритмов сортировок массивов необходимо учитывать, что ключ может полностью или частично совпадать с данными.
Способы и алгоритмы сортировки информации в массивах
Фактически любой алгоритм сортировки состоит из следующих составляющих этапов:
- Этап сравнения, определяющий упорядоченность пары компонентов.
- Этап перестановки, на котором меняется местами пара компонентов.
- Этап работы, собственно, сортирующего алгоритма, который выполняет сравнение и перестановку компонентов до тех пор, пока все компоненты множества не будут упорядочены.
Алгоритмы сортировки обладают большим практическим использованием. Они встречаются там, где ведётся обработка и сохранение больших информационных объемов. Большое число задач по обработке данных могут решаться проще, когда данные заранее упорядочены.
Универсального и самого лучшего алгоритма сортировки на текущий момент не существует. Но, обладая приблизительными характеристиками входных данных, можно выбрать метод, который будет работать оптимальным образом. Основными характеристиками, по которым может быть выполнена оценка алгоритмов, являются следующие параметры:
- Время сортировки считается основным параметром, характеризующим быстродействие алгоритма.
- Память является одним из параметров, который характеризуется тем, что некоторые алгоритмы сортировки требуют выделения дополнительной памяти под временное сохранение данных. При оценке применяемой памяти не учитывается место, занимаемое исходным массивом данных и независящие от входной последовательности затраты, к примеру, на сохранение кода программы.
- Устойчивость является параметром, отвечающим за то, что сортировка не изменяет взаимного расположения равных компонентов.
Естественность поведения является параметром, указывающим на эффективность методики при обработке уже отсортированных, или частично отсортированных данных. Алгоритм считается естественным, если учитывает эту характеристику входной последовательности и работает лучше.
Алгоритмы сортировки по сфере использования могут быть классифицированы следующим образом:
Алгоритмами внутренней сортировки являются такие алгоритмы, которые в процессе упорядочивания данных применяют только оперативную память (ОЗУ) компьютера.
- Алгоритмами внешней сортировки являются алгоритмы, который при осуществлении упорядочивания данных может использовать внешнюю память, как правило, жесткий диск. Внешняя сортировка предназначена для обработки больших списков данных, которые не могут быть помещены в оперативную память.
Внутренняя сортировка считается основой для всех алгоритмов внешней сортировки, так как отдельные фрагменты массива данных проходят сортировку в оперативной памяти и при помощи специального алгоритма сцепляются в один массив, упорядоченный по ключу.
Необходимо заметить, что внутренняя сортировка обладает большей эффективностью по сравнению с внешней, поскольку для обращения к оперативной памяти требуется значительно меньше времени, чем при обращении к внешним носителям.
Одним из основных алгоритмов внутренних сортировок является бинарная пирамидальная сортировка. Эта методика сортировки была предложена Дж. У. Дж. Уильямсом и Р.У. Флойдом ещё в 1964-ом году. Пирамидальная сортировка в определённом смысле может считаться модификацией такого метода, как сортировка выбором, с той лишь разницей, что минимальный (или максимальный) компонент из неотсортированной последовательности может быть выбран за меньшее число операций. Чтобы осуществить такой быстрый выбор из данной неотсортированной последовательности, необходимо построить некоторую структуру, которая именуется пирамидой.
Пирамидой является двоичное дерево с упорядоченными листьями, а корнем дерева считается наименьший или наибольший компонент. Пирамида может быть представлена в виде массива. Первым элементом пирамиды является наименьший или наибольший элемент, что определяется ключом сортировки.
Просеиванием считается выстраивание новой пирамиды по определённому алгоритму, а именно:
- Новый компонент следует поместить в вершину дерева.
- Затем он перемещается, то есть просеивается, по пути вниз на базе сравнения с дочерними компонентами.
- Процесс спуска следует завершить, когда результат сравнения с дочерними компонентами будет соответствовать ключу сортировки.
