блему сортировки, но нет желания изучать интерфейс системной сортировки, следует воспользоваться сортировкой методом Шелла; несколько позже вы решите, есть ли смысл прилагать дополнительные усилия, чтобы заменить его на более совершенный метод сортировки.

Упражнения

> 6.33. Устойчива ли сортировка методом Шелла?

6.34. Показать, как следует построить программу, реализующую сортировку методом Шелла с последовательностью шагов 1 8 23 77 281 1073 4193 16577 ... с непосредственным вычислением последовательных шагов, используя для этой цели метод, подобный примененному для разработки программы, вычисляющей шаги последовательности Кнута.

> 6.35. Представить диаграммы, соответствующие рис. 6.8 и 6.9 для ключей EASY QUESTION.

6.36. Определить время выполнения программы сортировки методом Шелла с последовательностью шагов 1 2 4 8 16 32 64 128 264 512 1024 2048 ... для сортировки файла, состоящего из целых чисел 1, 2, N на нечетных позициях и TV + 1, + 2, 2N на четных позициях.

6.37. Написать программу-драйвер, способную выполнять сравнения последовательностей шагов сортировки методом Шелла. Последовательность считываются из стандартного ввода, по одному значению шага в строке; затем используется для сортировки 10 файлов с произвольной организацией длины N, для TV = 100, 1000 и 10000. Подсчитать количество операций сравнения или замерить фактическое время выполнения сортировки для каждого файла.

6.38. Выполните эксперимент с целью определения, позволяет ли добавление или удаление отдельного шага улучшить последовательность шагов 1 8 23 77 281 1073 4103 16577... для Л= 10000.

6.39. Выполните эксперимент с целью определения значения х, которое обеспечивает минимальное время сортировки случайно распределенных файлов, если в последовательности 1 4 13 40 121 364 1093 3280 9841... для =10000 шаг 13 заменить на X.

6.40. Выполните эксперимент с целью определения значения а, которое обеспечивает минимальное время сортировки файлов с произвольной организацией для последовательности шагов 1, LaJ, LaH LaJ, LaH ...; где TV =10000.

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

6.42. Построить файл из 100 элементов, для которого сортировка методом Шелла с последовательностью шагов 1 8 23 77 выполняет максимально возможное количество операций сравнения, какое только удастся найти.

6.43. Доказать, что любое число, большее или равное (Л -\){к - \), может быть представлено в виде линейной комбинации (с неотрицательными коэффициентами) h и к, если h и к - взаимно простые числа. Совет: покажите, что если при делении на И два первых из Л -1 кратных к, имеют один и тот же остаток от деления на Л, то Л и А; должны иметь общий множитель.

6.44. Выполните эксперимент с целью определения значений h w к, которые обеспечивают наименьшие показатели времени сортировки файлов с произвольной организацией; в качестве шагов для сортировки 10000 элементов используется последовательность, подобная последовательности Пратта, при построении которой использованы h и к.

6.45. Последовательность шагов 1 5 19 41 109 209 505 929 2161 3905 ... построена путем слияния последовательностей 9 4 - 9 2 +1 и 4 - 3 2 +1 для / > 0. Сравните результаты использования этих последовательностей по отдельности с результатом использования их слияния на примере сортировки 10000 элементов.

6.46. Последовательность шагов 1 3 7 21 48 112 336 861 1968 4592 13776... получена на базе последовательности, состояшей из взаимно простых чисел, скажем, 1 3 7 16 41 101, с последующим построением треугольника из последовательности Пратта. В данном случае /-й ряд треугольника получен путем умножения первого элемента в /-1-ом ряду на /-й элемент базовой последовательности и путем умножения каждого элемента в /-1-ом ряду на /+1-ый элемент базовой последовательности. Проведите эксперименты с целью выявления базовой последовательности, которая превосходит указанную выше в процессе сортировки 10000 элементов.

6.47. Завершите доказательство лемм 6.7 и 6.8.

6.48. Построить реализацию, в основу которой положен алгоритм шейкер-сорти-ровки (упражнение 6.30), и сравнить со стандартным алгоритмом. Совет: следует воспользоваться такими последовательностями шагов, которые существенно отличаются от последовательностей, применяемых в стандартных алгоритмах.

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

На представленных диаграммах показана сортировка методом Шелла с последовательностью шагов 209109 4119 5 1 для файла с произвольной организацией, нормально распределенного файла, практически упорядоченного файла и случайно распределенного файла с 10различными значениями ключей (слева направо, сверху). Время выполнения каждого прохода зависит от того, насколько упорядочен файл к моменту начала прохода. После выполнения нескольких проходов все эти файлы будут упорядоченными одинаково; таким образом, время выполнения сортировки не очень чувствительно к виду входных данных.

******

6.7. Сортировка других типов данных

Несмотря на то что при исследовании алгоритмов целесообразно рассматривать их как процедуру, выполняющую размещение массивов чисел в порядке их возрастания или размещение символов в алфавитном порядке, необходимо признать, что эти алгоритмы, в основном, не зависят от типа сортируемых элементов, в связи с чем нетрудно сделать определенные обобщения. Мы подробно рассуждали о том, как разбить программы на отдельные независимые модули, ориентированные на работу с конкретными типами данных, а также о работе с абстрактными типами данных (см. главы 3 и 4); в настоящем разделе обсуждаются способы применения рассмотренных понятий с целью построения программных реализаций, интерфейсов и клиентских профамм для алгоритмов сортировки. В частности, будут рассмафиваться интерфейсы для:

элементов или обобщенных объектов, подлежащих сортировке

массивов элементов.

Тип данных item (элемент) предоставляет возможность использования профаммы сортировки для любых типов данных из числа тех, для которых определены некоторые виды базовых операций. Такой подход эффективен не только для простых, но и для абстрактных типов данных, в связи с чем мы перейдем к изучению множества программных реализаций. Интерфейс array (массив) менее критичен для нащей задачи; мы остановимся на нем с тем, чтобы получить навыки работы с многомодульной прОфаммой, которая имеет дело с несколькими типами данных. Мы рассмофим только одну из (достаточно простую) программных реализаций интерфейса array.

Программа 6.6 является клиентской программой, снабженной теми же общими функциональными средствами, что и функция main из программы 6.1, и пополненной возможностями манипуляции массивами и элементами, инкапсулированЦыми в отдельных модулях. Это обеспечивает, в частности, возможность тестирования программ сортировки на различных типах данных путем замены одних модулей на другие, не внося при этом каких-либо изменений в клиентскую профамму. Программа 6.6 обращается к интерфейсу с целью выполнить операции exch и compexch, используемые программными реализациями различных видов сортировки. Можно было бы настоять на том, чтобы эти программные средства были включены в интерфейс Item.h, однако реализации сортировок в программе 6.1, благодаря легко понимаемой семантике при определении операторов присваивания и оператора operator<, вполне подходят для нащей цели, так что проще содержать их в одном модуле, где они могут быть использованы всеми построенными реализациями для всех выбранных типов данных item. В заверщение программной реализации следует дать точное определение интерфейсов array и типа данных item и только после этого предлагать собственные программные реализации.

Программа 6.6. Драйвер сортировки массивов

Данный драйвер базовых сортировок массивов использует три явных интерфейса: первый для типа данных, который инкапсулирует операции, выполняемые на обобщенных элементах; следующий предназначен для функций exch и compexch несколько более высокого уровня, которые используются в программных реализациях сортировок; и третий - для функций, которые инициализируют и печатают (а также