Виды сортировок одномерного массива
Массив – это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип. В массивах объединены однотипные (логически однородные) элементы, упорядоченные по индексам, определяющим положение каждого элемента в массиве.
В качестве элементов массива можно использовать любой тип данных, включая структурированные, поэтому вполне правомерно существование массивов записей, массивов строк, массивов массивов и т. д.
Элементы, образующие массив, упорядочены таким образам, что каждому элементу соответствует совокупность номеров (индексов), определяющих его местоположение в общей последовательности.
Сортировка один из наиболее распространенных процессов обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами.
Сортировка к тому же еще и сама достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритмы нужно,исходя из конкретной постановки задачи. В общем, сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки - облегчить последующий поиск элементов в таком отсортированном множестве.
Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи "в порядке", и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики. Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Что может легче сортироваться, чем данные? Тем не менее,наш первоначальный интерес к сортировке основывается на том, что при построении алгоритмов мы сталкиваемся со многими весьма фундаментальными приёмами.
Почти не существует методов, с которыми не приходится встречаться при обсуждении этой задачи. В частности, сортировка - это идеальный объект для демонстрации огромного разнообразия алгоритмов.
Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте, т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес.Ограничив критерием экономии памяти наш выбор нужного метода среди многих возможных, мы будем сначала классифицировать методы по их экономичности, т. е. по времени их работы. Хорошей мерой эффективности может быть С - число необходимых сравнений ключей и М - число пересылок (перестановок) элементов. Эти числа суть функции от n - числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n* log n сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка n в квадрате сравнений ключей. Начинать разбор с прямых методов, не трогая быстрых алгоритмов, нас заставляют такие причины:
1. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
2.Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.
3.Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
Методы сортировки можно разбить в соответствии с определяющими их принципами на четыре категории:
1. Сортировки с помощью включения (by insertion).
2. Сортировки с помощью прямого выбора (by selection).
3. Сортировки с помощью обмена (by exchange).
