За счет такого упрощения рассматриваемое рекуррентное соотношение приобретает вид

NCn={N+ 1)С , + 2iV.

В третьих, разделив обе части на Л(Л+ 1) , получим рекуррентное соотношение, которое приобретает более компактную форму:

N + l N N + l

См-2 2 2

N-1 N N + 1

Это точное выражение почти равно сумме, которая легко аппроксимируется интегралом (см. раздел 2.3):

-dx = 2\RN,

\<k<n 1

откуда вытекает объявленный ранее результат. Обратите внимание на то, что 2N\nN~ \.39N\gN, так что среднее количество операций сравнения приблизительно лишь на 39 процентов больше, чем в самом лучшем случае.

Данный анализ предполагает, что сортируемый файл содержит случайно упорядоченные записи с различными ключами, однако реализации в программах 7.1 и 7.2 могут работать медленно в случаях, когда ключи не обязательно различны и не обязательно расположены в случайном порядке (рис. 7.4). Если сортировка применяется многократно или если она должна использоваться для упорядочения очень большого файла (или, в частности, если она должна использоваться как универсальная библиотечная функция для сортировки файлов с неизвестными характеристиками), следует рассмотреть несколько усовершенствований, предлагаемых в разделах 7.5 и 7.6, которые снижают вероятность того, что наихудший случай возникнет на практике, а также уменьшают среднее время выполнения сортировки где-то на 20 процентов.

Упражнения

7.6. Построить шесть файлов из 10 элементов, при упорядочении которых метод быстрой сортировки (профамма 7.1) выполняет то же число операций сравнения, что и в самом худшем случае (когда все элементы файла упорядочены).

7.7. Написать программу, вычисляющую точное значение Cyv, и сравнить это точное значение с приближенным значением 2Л1пЛдля = 10, 10, 10 и 10.

о 7.8. Сколько примерно операций сравнения выполнит быстрая сортировка (программа 7.1) для упорядочения файла из равных элементов?

, .4.l.-

РИСУНОК 7.4. ДИНАМИЧЕСКИЕ ХАРАКТЕРИСТИКИ БЫСТРОЙ СОРТИРОВКИ НА ФАЙЛАХ РАЗЛИЧНЫХ ТИПОВ

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

7.9. Сколько примерно операций сравнения понадобится быстрой сортировке (программа 7.1), чтобы выполнить сортировку файла, состоящего из элементов, которые имеют два различных значений ключа {к элементов с одним значением и N - к элементов с другим значением)?

7.10. Написать программу, которая строит файл, представляющий собой наиболее благоприятный случай для быстрой сортировки: файл из N различных элементов, обладающих таким свойством, что каждое его разбиение генерирует подфайлы, которые отличаются друг от друга по размерам максимум на 1 элемент.

7.3. Размер стека

Так же как и в главе 3, для выполнения быстрой сортировки можно воспользоваться стеком магазинного типа, рассматривая его как стек, в котором в виде сортируемых подфайлов содержится перечень работ, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подфайла, он выталкивается из стека. После разделения файла получаются два подфайла, требующих дальнейщей обработки, которые и заталкиваются в стек. В рекурсивной реализации, представленной программой 7.1, стек, который поддерживается системой, содержит именно эту информацию.

Что касается файлов с произвольной организацией, то максимальный раздел стека пропорционален значению log N (см. раздел ссылок), однако в условиях вырожденного случая стек может расширяться до размеров, пропорциональных N, как показано на рис. 7.5. В самом деле, наиболее трудный случай имеет место тогда, когда файл уже отсортирован. Потенциальная возможность увеличения размеров стека до пропорциональных размерам сортируемого файла в условиях рекурсивной реализации быстрой сортировки представляет собой не очевидную, но в то же время вполне реальную проблему: в условиях этого метода сортировки всегда используется стек, а в вырожденном случае при работе с файлом большого размера подобное обстоятельство может послужить причиной аварийного останова программы ввиду нехватки памяти. Такое поведение совершенно недопустимо для библиотечной программы сортировки. (По всей вероятности, мы скорее столкнемся с проблемой недопустимо длительной сортировки, нежели с проблемой нехватки памяти.) Трудно гарантировано исключить подобное поведение программы, но как будет показано в разделе 7.5, нетрудно предусмотреть специальные средства, которые делают вероятность возникновения таких вырожденных случаев исключительно малой.

РИСУНОК 7.5. РАЗМЕР СТЕКА ДЛЯ БЫСТРОЙ СОРТИРОВКИ.

Рекурсивный стек для быстрой сортировки не становится больше для файлов с произвольной организацией, но в то же время он может потребовать дополнительного пространства при работе с вырожденными файлами. На диаграмме представлены размеры стеков для двух файлов с произвольной организацией (слева, в центре) и размеры для частично упорядоченных файлов (справа).