Введение
Алгоритмы сортировки – это определённые пошаговые действия, в результате которых все элементы произвольной последовательности удаётся расположить в порядке их неубывания.
В зависимости от задействованной в процессе сортировки компьютерной памяти принято различать алгоритмы внутренней и внешней сортировки.
Внутренняя сортировка – это упорядочение последовательности элементов, когда она целиком находится в оперативной памяти. Такие алгоритмы применяются к относительно небольшим по своему объёму последовательностям (например, при сортировке элементов в массиве).
Внешняя сортировка – это упорядочение последовательности элементов с использованием не только оперативной, но и внешней памяти. Она используется, тогда, когда сортируемая последовательность не может быть целиком размещена в оперативной памяти (например, при сортировке данных в файлах и в других ситуациях, когда количество сортируемых элементов очень велико).
Таким образом, внутренние сортировки используются в случаях, когда все сортируемые данные обозримы, а внешние – когда эти данные невозможно полностью одновременно держать в области видимости.
Если говорить о сложности алгоритмов сортировки, то она в любом случае будет зависеть от количества элементов сортируемой последовательности. Также немаловажным является не только объём входных данных, но и их качество. В зависимости от этого фактора выделяют такие возможные ситуации:
- лучший случай (если последовательность уже изначально была отсортирована);
- худший случай (если последовательность оказалась отсортированной, но в обратном порядке);
- средний случай (если последовательность содержит элементы в абсолютно произвольном порядке).
Алгоритмы внутренней сортировки
Большинство алгоритмов внутренней сортировки предполагают выполнение сортировки массива без использования каких-либо дополнительных массивов для хранения временных данных.
Стандартно элементарным шагом внутренней сортировки является некоторый обмен местами двух элементов последовательности.
Выбор этих элементов на каждом шаге сортировки будет зависеть от вида выбранного алгоритма для сортировки и его основных принципов.
К наиболее популярным методам внутренней сортировки относятся следующие методы.
Сортировка подсчётом.
Здесь используется дополнительный (результирующий) массив. Место каждого элемента в результирующем массиве определяется как единица + количество элементов сортируемой последовательности, которые оказались меньше данного элемента.
Пузырьковая сортировка.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый такой проход элементы последовательно сравниваются попарно и, если порядок в паре оказывается неправильный, то сразу же выполняется обмен местами этих элементов. Отсюда и название данного алгоритма, так как в ходе выполнения указанных последовательных действий каждый элемент, расположенный не на своем месте, постепенно "всплывает" до нужной позиции, подобно пузырьку в воде.
Существуют более эффективные варианты пузырьковой сортировки. К ним относятся шейкерная сортировка и сортировка Шелла. Такие алгоритмы позволяют на каждом шаге сокращать длины просматриваемых последовательностей чисел за счёт учитывания уже отсортированых частей массива.
Сортировка простыми вставками.
При таком подходе весь массив разбивается на две части, где его левая часть является упорядоченной, а правая – неупорядоченной. На каждом шаге алгоритма требуется сначала выбрать первый элемент из правой части и переместить его в левую на соответствующую позицию, сохраняя её упорядоченность; а затем расширить левую (сократить правую) часть на один элемент. Весь этот процесс сортировки начинается, когда левая часть состоит только из одного элемента, и продолжается до тех пор, пока правая часть не окажется пустой.
Сортировка простым выбором.
Здесь массив также разделяется на две части: слева – упорядоченная, а справа – нет. На каждом шаге данного алгоритма определяется минимальный элемент в правой части, и затем он меняется с первым элементом массива. Далее необходимо расширить левую (сократить правую) часть на один элемент. Процесс этого алгоритма начинается, когда левая часть массива пуста, и завершается, когда правая часть состоит всего из одного элемента.
Сортировка слиянием.
Данный вид сортировки предполагает разбиение массива на два подмассива, в каждом из которых выполняется сортировка с использованием рекурсивного вызова алгоритма во всех отдельных подмассивах, пока их размеры не станут равными единице. Далее выполняется слияние отсортированных подмассивов в один.
Быстрая сортировка.
Она начинается с разбиения исходного массива на две области. Обе эти части находятся слева и справа от некоторого отмеченного элемента, называемого опорным. В итоге применения данного алгоритма одна часть массива будет содержать элементы меньшие опорного, а другая – элементы большие, чем опорный.
Далее приведён пример программного кода на языке C++, в котором реализован алгоритм быстрой сортировки:
Рисунок 1. Программный код. Автор24 — интернет-биржа студенческих работ
Все остальные из перечисленных выше видов сортировок можно запрограммировать аналогичным образом, используя определённую стратегию, предписанную алгоритмом.
Алгоритмы внешней сортировки
Так как при программном взаимодействии с любым файлом возможен только последовательный доступ к его элементам, то алгоритмы, позволяющие выполнять сортировку в файлах, основываются на следующем принципе: на каждом шаге из файла берутся нужные элементы, после чего они добавляются в какое-то новое место в файле.
При работе с файлами допустимы следующие операции:
- распределение – переписывание части файла в новый файл;
- слияние – объединение разделённых файлов.
Именно на этих действиях основываются все методы внешней сортировки.
Также важно понятие серии (или отрезка) файла, которая представляет собой некоторую упорядоченную часть файла. Поэтому здесь можно сказать, что сортировка – это преобразование файла из n серий (где n>1) в файл, состоящий всего из 1 серии.
Ещё с внешними сортировками связаны такие понятия как фаза (действие по однократной обработке всего набора сортируемых элементов) и проход (наименьший этап, повторение которого образует весь процесс сортировки.
Теперь перечислим основные методы внешних сортировок:
- алгоритм прямого слияния;
- алгоритм естественного слияния;
- многопутевое слияние;
- многофазная сортировка.
