2020-01-14
130
Меньшие или равные граничному элементу, а в другой части – только большие или
Равные.
Например, если выбрать в качестве граничного элемента значение 8, то после
Переупорядочения массив окажется в состоянии, показанном на рис. 7. Затем тот же
Самый процесс независимо выполняется для левой и правой частей массива.
Рис. 7.. Массив после разделения на две части и переупорядочения элементов в них.
Процесс разбиения и переупорядочения частей массива можно реализовать ре-
курсивно. Индекс граничного элемента вычисляется как индекс среднего элемента:
95
(first + last)/2
где "first" и "last" являются индексами первого и последнего элементов обрабаты-
Ваемой части массива.
Далее подробно рассматривается процедура переупорядочения элементов мас-
Сива.
Индексы "left_arrow" и "right_arrow" определим как индексы крайних элемен-
Тов обрабатываемой части массива (которая подвергается разбиению, см. рис. 8).
Рис. 8.. Значения индексов "left_arrow" и "right_arrow" перед нача-
Лом процедуры переупорядочения.
|
|
|
В процессе переупорядочения индексы "left_arrow" и "right_arrow" смещают-
ся в направлении граничного элемента. Так, "right_arrow" перемещается влево, пока
Значение элемента не окажется меньше или равно граничному значению (рис. 9).
Рис. 9.. Обнаружение левого и правого элементов для обмена.
Аналогично, "left_arrow" смещается вправо, пока не встретится элемент,
Больший или равный граничному. В нашем примере этот элемент расположен в нача-
Ле массива (рис. 9). Теперь значения двух найденных элементов массива меняются
Местами (рис. 10).
Рис. 10.. Состояние массива после обмена двух элементов.
После обмена двух элементов "right_arrow" продолжает смещаться влево.
Смещение прекращается, когда находится очередной элемент, меньший или равный
Граничному (рис. 11).
Рис. 11.. Справа обнаружен элемент для обмена.
Индекс "left_arrow" смещается вправо, пока не встретится элемент, требую-
Щий перестановки (рис. 12).
Рис. 12.. Слева обнаружен элемент для обмена.
Значения найденных элементов меняются местами (рис. 13).
96
Рис. 13.. Состояние массива после обмена второй пары элементов.
Переупорядочение частей массива прекращается после выполнения условия
"left_arrow > right_arrow". В состоянии на рис. 13 это условия ложно, поэтому
"right_arrow" продолжает смещаться влево, пока не окажется в положении, показан-
Ном на рис. 14.
Рис. 14.. Справа обнаружен элемент для обмена.
Перемещение "left_arrow" приведет к состоянию, показанному на рис. 15. По-
скольку при перемещении вправо надо найти элемент, больший или равный "pivot",
то "left_arrow" прекращает перемещение после достижения граничного элемента.
|
|
|
Рис. 15.. Левый элемент для обмена совпадает с граничным.
Теперь выполняется обмен, включающий граничный элемент (такой обмен до-
Пустим), и массив переходит в состояние, показанное на рис. 16.
Рис. 16.. Состояние массива после обмена третьей пары элементов.
После обмена элементов "right_arrow" перемещается влево, а "left_arrow" –
Вправо (рис. 17).
Рис. 17.. Переупорядочение прекращается после прохождения индексами се-
Редины массива.
В состоянии, показанном на рис. 17, становится истинным условие завершения
процедуры переупорядочения "left_arrow > right_arrow". Поэтому первую процеду-
Ру разбиения и переупорядочения массива можно считать выполненной.
Ниже приведена функция на Си++, в которой рекурсивно реализован алгоритм
сортировки QuickSort:
void quick_sort(int list[], int left, int right)
{
int pivot, left_arrow, right_arrow;
97
left_arrow = left;
right_arrow = right;
pivot = list[(left + right)/2];
do {
while (list[right_arrow] > pivot)
right_arrow--;
while (list[left_arrow] < pivot)
left_arrow++;
if (left_arrow <= right_arrow)
{
swap(list[left_arrow], list[right_arrow]);
left_arrow++;
right_arrow--;
}
} while (right_arrow >= left_arrow);
if (left < right_arrow)
quick_sort(list, left, right_arrow);
if (left_arrow < right)
quick_sort(list, left_arrow, right);
}
Программа 7.1.
Сводка результатов
На Си++ можно писать рекурсивные функции. В лекции кратко описан порядок
Выполнения рекурсивных функций и назначение стека. Для любой рекурсивной
Функции можно разработать итерационный аналог. В лекции указаны преимущества
И недостатки рекурсивной реализации. В качестве примера приведен известный алго-
ритм быстрой сортировки QuickSort и его рекурсивная реализация на Си++.
Упражнения
Упражнение 1
Последовательность чисел Фибоначчи может быть определена следующим образом:
• a (1) = 1
• a (2) = 1
• для всех n >2 a (n) = a (n -1) + a (n -2)
Это определение позволяет сгенерировать такую последовательность:
1, 1, 2, 3, 5, 8, 13, 21,...
Напишите на Си++ функцию "fibonacci(...)", которая вычисляет числа Фи-
боначчи по их порядковому номеру, например, fibonacci(7)==13.
Упражнение 2
Для выполнения этого упражнения используйте программу 5.1 из 7-й лекции.
а) Напишите две рекурсивных функции "print_list_forwards(...)" и
"print_list_backwards(...)", которые должны печатать на экране содержимое
Связного списка, рассмотренного в 7-й лекции, соответственного _______в прямом и
98
обратном порядке. (Функция "print_list_forwards(...)" должна вести себя
точно так же, как и функция "print_list(...)" из 7-й лекции). Измените про-
Грамму 5.1 из 7-й лекции так, чтобы проверить свои функции. Ваша программа
должна выдавать на экран следующие сообщения:
Введите первое слово (или '.' для завершения списка): это
Введите следующее слово (или '.' для завершения списка): короткое
Введите следующее слово (или '.' для завершения списка): тестовое
Введите следующее слово (или '.' для завершения списка): сообщение
Введите следующее слово (или '.' для завершения списка):.
ПЕЧАТЬ СОДЕРЖИМОГО СПИСКА В ПРЯМОМ ПОРЯДКЕ:
Это короткое тестовое сообщение
ПЕЧАТЬ СОДЕРЖИМОГО СПИСКА В ОБРАТНОМ ПОРЯДКЕ:
Сообщение тестовое короткое это
Подсказка: при разработке функции " print_list_backwards() " еще раз посмотрите
На программу 2.1.
Б) Напишите и протестируйте итерационный (т.е. нерекурсивный) вариант функ-
ции "print_list_backwards(...)". (Какой вариант функции вам показался про-
Ще в разработке?)
Упражнение 3
Даны два положительных целых числа m и n таких, что m < n. Известно, что
наибольший общий делитель чисел m и n совпадает с наибольшим общим делителем
чисел m и (n - m). С учетом этого свойства напишите рекурсивный вариант функции
"greatest_common_divisor(...)", которая принимает два положительных целых пара-
