Контрольная работа структуры и алгоритмы обработки данных. Контрольная работа. Контрольная работа по предмету Структуры и алгоритмы обработки данных
 Скачать 100.46 Kb.
|
|
Жирные подчёркнутые символы обозначены как те, которым требовалась перестановка. Красные символы – символы которые установлены на свои места. Отсортированный набор обозначен зелёным цветом. Первые и последние 4 символа обозначены как «поворотные» (АААВ и НОПХ), а также оставшаяся часть массива, в которой перестановки уже не нужны (ЕЛНН). На первом проходе выполняется ровно 11 сравнений и максимально 11·3 = 33 перестановки. На втором проходе выполняется ровно 10 сравнений и максимально 10·3 = 30 перестановок. На третьем проходе выполняется ровно 9 сравнений и максимально 9·3 = 27 перестановок и т.д. На последнем проходе выполняется ровно одно сравнение и максимально 1·3 = 3 перестановки. Таким образом: 1. общее число сравнений С = ((11 + 1) / 2)× 11 = 66; 2. общее число перестановок М = С × 3 = 198. Ответ: АААВЕЛНННОПХ; 66 сравнений, 198 перестановок. Задание 3. Для набора из 12 символов ФИО студента выполнить сортировку методом Шелла, предварительно необходимо определить последовательность шагов по формуле Кнута. Подсчитать количество необходимых сравнений и перестановок. Решение: Набор символов ФИО: ПЛЕХАНОВААНН При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места. Сортировка методом Шелла пытается повысить скорость работы за счет более быстрого перемещения элементов, находящихся далеко от нужных им позиций. Она предполагает перемещение таких элементов большими "прыжками" через несколько элементов одновременно, уменьшая размер "прыжков" и, в конце концов, окончательная установка элементов в нужные позиции выполняется с помощью классической сортировки методом вставок. Последовательность H из m возрастающих шагов имеет следующий вид: H= (h1, h2, …, hm), где h1=1. Метод Шелла состоит в последовательном проведении hi-сортировки, i=m, m-1,…,1. Эффективность метода зависит от выбора значений шагов. В частности, Кнут предложил последовательность значений шагов, вычисляемую по следующей формуле: h1=1; hi=2·hi-1+1; i=2,…,m;  .Для n=12 имеем:  . Поэтому h1=1, h2=2·1+1=3Сначала строим таблицу выполнения 3-сортировки. Обозначим: Красный цвет: проверяемый очередной элемент. Синий цвет: сравниваемый неперемещаемый элемент. Зелёный цвет: сравниваемый и обмениваемый с проверяемым элемент. Сортируем:
|