СОРТИРОВКА МАССИВОВ

В данной главе представлены принципиальные алгоритмы внутренней сортировки. Задача сортировки состоит в упорядочивании элементов в неубывающем (невозрастающем) порядке. Основным условием, предъявляемым к алгоритмам сортировки, является экономное использование доступной памяти. Это предполагает, что перестановки элементов с целью их упорядочивания должны выполняться на том же месте, т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес.

Эффективность алгоритмов сортировки массива можно оценить по таким критериям, как число необходимых сравнений элементов (С) и число перестановок элементов (М).

Эти числа фактически являются функциями от п - числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка п * log(/?) сравнений, рассмотрим несколько простых и очевидных методов, называемых прямыми, где требуется порядка п сравнений элементов. Разбор прямых методов целесообразен ввиду следующих причин:

Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

Программы этих методов легко понимать, и они коротки. Следует помнить, что сами программы также занимают память.

Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых п прямые методы оказываются быстрее, хотя при больших п их использовать, конечно, не следует.

Методы сортировки «на том же месте» можно разбить в соответствии с определяющими их принципами натри основные категории:

  • • сортировки с помощью включения (by insertion);
  • • сортировки с помощью выбора (by selection);
  • • сортировки с помощью обмена (by exchange).

Все рассматриваемые алгоритмы будут оперировать массивом а, в котором будут храниться переставляемые на месте элементы. Данный массив объявляется следующим образом:

Сортировка с помощью прямого включения

При сортировке элементов массива с помощью прямого включения массив делят на две части: отсортированную, или «готовую», ..., <т,_i и неотсортированную, или «исходную», ah ..., ап.

В начале работы алгоритма в качестве отсортированной части массива принимается только один первый элемент, а в качестве неотсортированной части - все остальные элементы.

На каждом шаге, начиная с / = 2 и увеличивая i каждый раз на единицу, из неотсортированной последовательности извлекается /-й элемент и вставляется в отсортированную так, чтобы не нарушить в ней упорядоченности элементов. Каждый шаг алгоритма включает четыре действия:

Взять /-й элемент массива, он же является первым элементом в неотсортированной части, и сохранить его в дополнительной переменной.

Найти позицию j в отсортированной части массива, куда будет вставлен /-й элемент, значение которого теперь хранится в дополнительной переменной. Вставка этого элемента не должна нарушить упорядоченности элементов отсортированной части массива.

Сдвиг элементов массива с / — 1 позиции по у-ю на один элемент вправо, чтобы освободить найденную позицию для вставки.

Вставка взятого элемента в найденную у- ю позицию.

На рис. 3.1 приведены два первых шага работы алгоритма сортировки с помощью прямого включения. Отсортированная и неотсортированная части отделены вертикальной чертой.

Первые два шага алгоритма сортировки с помощью прямого включения

Рис. 3.1. Первые два шага алгоритма сортировки с помощью прямого включения

На рис. 3.2 показан пример работы алгоритма сортировки массива из шести элементов. Отсортированная часть массива подчеркнута.

Анализ алгоритма сортировки с прямым включением. Число сравнений ключей (С,) при /-м проходе самое большее равно i - 1, самое меньшее - 1. Если предположить, что все перестановки из п элементов равновероятны, то среднее число сравнений -it 2. Число же перестановок Mi равно С,- + 2.

Пример сортировки с помощью прямого включения

Рис. 3.2. Пример сортировки с помощью прямого включения

Данный алгоритм показывает наилучшие результаты работы в случае уже упорядоченной исходной части массива, наихудшие - когда элементы первоначально расположены в обратном порядке. Алгоритм с прямым включением можно легко улучшить, если обратить внимание на то, что готовая последовательность, в которую надо вставить новый элемент, сама уже упорядочена. Естественным является остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением (binary insertion).

К несчастью, улучшения, порожденные введением двоичного поиска, касаются лишь числа сравнения, а не числа необходимых перестановок. А поскольку движение элемента, т. е. самого элемента и связанной с ним информации занимает значительно больше времени, чем сравнение двух ключей, то фактически улучшения не столь уж существенны, ведь важный член М так и продолжает оставаться порядка я2. И на самом деле сортировка уже отсортированного массива потребует больше времени, чем в случае последовательной сортировки с прямыми включениями.

Этот пример показывает, что «очевидные улучшения» часто дают не столь уж большой выигрыш, как это кажется на первый взгляд, а в некоторых случаях (происходящих на самом деле) эти «улучшения» могут фактически привести к ухудшениям. После всего сказанного сортировка с помощью включения уже не кажется столь удобным методом для цифровых машин: включение одного элемента с последующим сдвигом на одну позицию целой группы элементов не экономно. Остается впечатление, что лучший результат дадут методы, где передвижка, пусть и на большие расстояния, будет связана лишь с одним-единственным элементом.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >