Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача 7.6. Рекурсивные функции





 

Написать программу упорядочивания массива методом быстрой сортировки, используя рекурсию.

 

Пришло время выполнить обещание, данное на третьем семинаре, — показать рекурсивную реализацию методе быстрой сортировки. Если вы не знаете, что такое рекурсивные функции, загляните в Учебник на с. 82. Говоря кратко, рекурсивной называется функция, в которой имеется обращение к ней самой. Освежите в памяти алгоритм быстрой сортировки, который мы рассматривали, решая задачу 3.3. Там. использовалась «процедура разделения», применяемая к фрагменту массива (изначально - ко всему массиву). На каждом шаге образовывались две половинки текущего фрагмента, и к ним снова нужно было применять процедуру разделения. То есть по своей сути алгоритм является рекурсивным, и если не здесь применять рекурсивные функции, то где?..

 

К счастью, любая функция в программе на C++ может вызываться рекурсивно. При этом в стеке выделяется новый участок памяти для размещения копий параметров, а также автоматических и регистровых переменных, поэтому предыдущее состояние выполняемой функции сохраняется, и к нему впоследствии можно вернуться (так и произойдет, если только ваша программа где-нибудь не зависнет).

 

Одна из возможных версий программы сортировки приведена ниже.

 

#include < iostream.h> void qsort(float* array, int left, int right); int main() { const int n = 10; float arr[n]; int i, l, r; cout < < " Введите элементы массива: "; for (i = 0; i < n, i++) cin > > arr[i]; l = 0, r = n – l; // левая и правая границы начального фрагмента qsort(arr, l, r); // 1 for (i = 0; i < n; iiii++) cout < < arr[i] < < ' '; return 0; } void qsort(float* array, int left, int right) { int i = left, j = right; float middle = array[(left + right) / 2]; float temp; while (i < j) { while (array[i] < middle) i++; while (middle < array[j]) j--; if (i < = j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } if (left < j) qsort(array, left, j); // 2 if (i < right) qsort(array, i, right); // 3 }

 

Мы не будем подробно анализировать эту программу, поскольку алгоритм вам знаком по задаче 3.3. Отметим только, что процедура разделения реализована здесь в виде рекурсивно вызываемой функции qsort(), в теле которой есть два обращения к самой себе: в операторе 2 — для сортировки левой половинки текущего фрагмента, и в операторе 3 - для сортировки его правой половинки. Надеемся, что сравнение этой программы с предыдущей нерекурсивной версией (задача 3.3) вызовет у вас истинное эстетическое наслаждение1.

 

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

 







Дата добавления: 2014-11-10; просмотров: 586. Нарушение авторских прав; Мы поможем в написании вашей работы!




Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...


Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...


Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

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

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

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

Типология суицида. Феномен суицида (самоубийство или попытка самоубийства) чаще всего связывается с представлением о психологическом кризисе личности...

ОСНОВНЫЕ ТИПЫ МОЗГА ПОЗВОНОЧНЫХ Ихтиопсидный тип мозга характерен для низших позвоночных - рыб и амфибий...

Принципы, критерии и методы оценки и аттестации персонала   Аттестация персонала является одной их важнейших функций управления персоналом...

Studopedia.info - Студопедия - 2014-2025 год . (0.01 сек.) русская версия | украинская версия