3. Прямые методы сортировки массивов
Сортировка
В общем случае сортировка (упорядочение) представляет собой процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном списке объектов.
Цель
сортировки заключается в упорядочивании
исходной последовательности элементов
а1,
a2,
..., аn
таким образом, чтобы получить такую
перестановку
,
,
...,
, для которой выполняется условие
где f - некоторая функция сортировки, которая задает отношение порядка. Порядок может отражать возрастание или убывание некоторых значений, может быть алфавитным, хронологическим и др.
Сортируемые элементы представляются записями, каждая из которых имеет поле ключа, и поле данных. Поле ключа содержит некоторое число, обычно целое, и записи упорядочиваются по значению ключа.
Прямые методы сортировки массивов
В прямых методах сортировки перестановки элементов должны быть выполнены в одном массиве (минимальная по памяти сортировка).
Выделяют следующие прямые методы сортировки:
- сортировка обменами ("пузырьковая сортировка");
- сортировка выбором;
- сортировка простыми вставками.
Сортировка обменами. Слева направо поочередно сравниваются ключи двух соседних элементов. Если их порядок не соответствует заданному отношению, то эти элементы меняются местами. Далее осуществляется сдвиг вправо па один элемент и анализируется следующая пара. Просмотр массива завершается после сравнения ключей элементов, находящихся в предпоследней (n-1)-й и последней n-й позициях.
После первого просмотра массива элемент с наибольшим значением ключа займет позицию n, а с наименьшим - переместится на одну позицию к началу массива.
Второй просмотр выполняется аналогично, но завершается сравнением элементов в позициях n-2 и n-1, поскольку максимальный элемент уже занял свою позицию.
Таким образом, на каждом просмотре очередные наибольшие элементы будут занимать позиции n, n-1, n-2, ..., 2, а всего потребуется n-1 просмотров.
Ускорение работы алгоритма может быть достигнуто следующим образом. На каждом просмотре фиксируется факт наличия или отсутствия обменов. Если на очередном просмотре обменов не было, то элементы упорядочены и сортировка завершена.
Сортировка простыми вставками. Массив делится на две части - отсортированную и неотсортированную. В начале работы в отсортированную часть входит только один первый элемент. Алгоритм выполняет n-1 проход, на каждом из которых поочередно выбираются элементы из неотсортированной части и вставляются в отсортированную часть таким образом, чтобы не нарушить в ней упорядоченность элементов.
На некотором i-м проходе элементы a1, a2, ..., ai составляют отсортированную часть, а элементы ai+1, ai+2, …, an - неотсортированную. Если f(ai) ≤ f(ai+1), то элемент ai+1 включается в отсортированную часть. В противном случае значение ai+1 временно сохраняется в переменной s = ai+1, а элемент ai сдвигается на одну позицию вправо.
Далее ключ f(s) поочередно сравнивается с ключами следующих элементов из отсортированной части справа налево, т.е. с ключами f(ak), k = i-1, i-2, ..., 1. Если f(S) < f(ak), то элемент ak сдвигается на одну позицию, вправо. В противном случае элемент S записывается в k+1-ю позицию.
Скорость сортировки простыми вставками можно увеличить, если для поиска позиции элемента ai+1 в отсортированной части использовать метод бинарного поиска, так как элементы упорядочены. Это уменьшает общее число сравнений от O(n2) до O(n log2n), но количество перестановок элементов при этом не уменьшается и имеет порядок O(n2).
Сортировка выбором. Просматривается массив и находится наименьший элемент. Затем этот элемент меняется местами с первым элементом. Но втором шаге отыскивается минимальный элемент в диапазоне от второго до n-го элемента и меняется местами со вторым элементом. Процесс повторяется для всех элементов до (n-1)-го элемента.
Эффективность прямых методов сортировки оценивается количеством необходимых элементарных операций и числом перестановок элементов в процессе сортировки. Как в среднем, так и в худшем случае, количество элементарных операций для всех прямых методов сортировки имеет порядок O(n2). Однако, если размер записи большой, то операция перестановки пары элементов местами, которая присутствует во всех алгоритмах, будет занимать больше времени, чем другие операции.
Поэтому целесообразно сравнить алгоритмы сортировки по количеству перестановок. Для алгоритмов сортировки обменами и вставками среднее число перестановок оценивается как n2/4. Сортировка выбором предполагает n-1 перестановку, что делает этот алгоритм более эффективным для наихудшего случая, когда элементы исходного массива расположены в обратном порядке.
В целом экспериментальные исследования показывают, что для случайного порядка элементов сортировка выбором по эффективности незначительно уступает сортировке простыми вставками. Однако, чем ближе массив к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Алгоритм сортировки обменами является наихудшим.
В общем случае, если необходимо упорядочить длинные записи, целесообразно работать не с массивом записей, а с массивом указателей на записи. После упорядочения массива указателей сами записи можно расположить в нужном порядке за время пропорциональное этому количеству записей.