ПРАКТИЧЕСКОЕ
ЗАНЯТИЕ № 12
Тема: «Программирование
рекурсивных алгоритмов»
Цель: изучить правила составления рекурсивных
алгоритмов, научиться решать задачи с помощью рекурсии, научиться выполнять быструю
сортировку Хоара в одномерных массивах
Ход работы
Теоретическое обоснование
Быстрая сортировка (Хоара)
Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым алгоритмом сортировки из тех, что оперируют сравнениями.
Этот алгоритм является ярким примером реализации принципа «разделяй и властвуй». Как показывают теоретические выкладки, наиболее эффективным в общем случае оказывается разделение задачи на две равные по сложности части, что здесь и делается. На каждом шаге алгоритма сначала выбирается «средний» элемент, затем переставляются элементы массива так, что массив разделился на две части. Первая часть содержит элементы меньше «среднего» и, возможно, равные ему. Вторая часть содержит элементы больше «среднего» и, возможно, равные ему. После такого деления массива остается только отсортировать его части по отдельности, с которыми поступаем аналогично (делим на две части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован (рис. 6). В случае, когда массив содержит только одинаковые элементы, выбор «среднего» элемента не производится и сортировка не осуществляется.
Рисунок 6 – Сортировка Хоара
Разделение массива на две части производится следующим образом. Устанавливаем один курсор на левую границу массива, а второй – на правую границу. Затем осуществляем перемещение курсоров навстречу друг другу до тех пор, пока они не пересекутся. При перемещении курсоров сравниваем значения текущих элементов со «средним». Находим левый текущий элемент, больший «среднего», и правый текущий элемент, меньший «среднего» (т. е. элементы, которые находятся «не на своем месте»). Осуществляем обмен этих элементов.
Код сортировки методом Хоара:
1. Организовать процедурами:
- ввод и вывод данных массива;
- быструю сортировку и вывод результата.
2. Отсортировать элементы на главной и побочной диагоналях двумерного массива методом Хоара.
3. Получить пять массивов случайных чисел. Найти суммы элементов в каждом массиве. По возрастанию величины суммы вывести соответствующие массивы.