Сравнительный анализ эффективности методов сортировки

При обработке данных важно знать информационное поле данных и размещение их в машине.

Различают внутреннюю и внешнюю сортировку:

- внутренняя сортировка - сортировка в оперативной па­мяти (по внутренним ключам);

- внешняя сортировка - сортировка во внешней памяти (по внешним ключам).

Мы будем рассматривать методы сортировки по внешним ключам; на том же месте; методы устойчивой сортировки.

Сортировка - это расположение данных в памяти в регу­лярном виде по их ключам. Регулярность рассматривают как возрастание (убывание) значения ключа от начала к концу в массиве.

Рис. 6.1. Сортировка.

Если сортируемые записи занимают большой объем па­мяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, сортировку производят в таблице адре­сов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.

При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же порядке, что и в ис­ходном файле. Это - устойчивая сортировка (взаимное расположение одинаковых ключей не меняется).

Эффективность сортировки можно рассматривать с не­скольких критериев:

- время, затрачиваемое на сортировку;

- объем оперативной памяти, требуемой для сортиров­ки;

- время, затраченное программистом на написание про­граммы.

Выделяем первый критерий, поскольку будем рассмат­ривать только методы сортировки «на том же месте», то есть, не резервируя для процесса сортировки дополнительную па­мять. Эквивалентом затраченного на сортировку времени можно считать количество сравнений при выполнении сор­тировки и количество перемещений.

Порядок числа сравнения при сортировке лежит в пре­делах от О (n log n) до О (n²); О(n) - идеальный и недос­тижимый случай.

Различают следующие методы сортировки:

- строгие (прямые) методы;

- улучшенные методы.

Строгие методы:

1) метод прямого включения.

Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (вклю­чая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположе­ны в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает про­цесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.

Количество сравнений в худшем случае, когда массив от­сортирован противоположным образом, Cmax = n(n - 1)/2, т. е. - О (n²). Количество перестановок Mmax = Cmax + 3(n-1), т.е. - О (n²). Если же массив уже отсортирован, то число сравнений и перестановок минимально: Cmin = n-1; Мmin = 3(n-1).

2) метод прямого выбора.

Число сравнений ключей Сi, очевидно, не зависит от на­чального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для С при любом расположении клю­чей имеем:

С=n(n-1)/2

Порядок числа сравнений (эффективности), таким образом, O(n )

Число перестановок минимально М = 3(n - 1) в случае изначально упорядоченных ключей и максимально, M = 3(n - 1) + С, т.е. порядок O(n ), если первоначально ключи располагались в обратном порядке.

В худшем случае сортировка прямым выбором дает по­рядок n², как для числа сравнений, так и для числа переме­щений.

3) метод прямого обмена.

Число сравнений Сmах = n(n-1)/2, O(n ).

Число перемещений Mmax=3Cmax=3n(n-l)/2, O(n ).

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда по­лучаем минимальное число сравнений

Cmin=n-l, O(n ), а перемещения вообще отсутствуют.

Сравнительный анализ прямых сортировок показывает, что обменная "сортировка" в классическом виде представля­ет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены при­веденные выше усовершенствования, то для достаточно упо­рядоченных массивов пузырьковая сортировка даже имеет преимущество.

Эффективность этих трех методов примерно одинакова.

Улучшенные методы:

1) быстрая сортировка.

О(n log n) - самый эффективный метод.

2) сортировка Шелла.

He доказано, какие расстояния дают наилучший резуль­тат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов (в обратном порядке): 1, 3, 7, 15, 31,... То есть: h = h + 1, t = log n - 1. При такой организации алгоритма его эффектив­ность имеет порядок О (n ).