Функции и структура программ

Другой хороший пример рекурсии, это quicksort, алгоритм сортировки, разработанный CAR Hoare в 1962 году. Имея массив, выбирается один элемент и остальные розбивается на две группы - те, которые меньше выбранного элемента и те, которые больше или равны ему. То же самое затем применена рекурсивно к этим двум группам. Когда подгруппа осталась с мешне чем двумя элементами, она не требует никакого сортировки; это останавливает рекурсию.

Наша версия quicksort не является самой быстрой из возможных, но это одна из самых простых. Мы используем средний элемент каждой части массива для дальнейшего разделения.
/ * Qsort: сортирует v [left] ... v [right] в возрастающей последовательности * /
void qsort (int v [], int left, int right)
{
int i, last;
void swap (int v [], int i, int j);

if (left> = right) / * ничего не делать, если массив * /
return; / * содержит менее двух элементы * /
swap (v, left, (left + right) / 2); / * переместить элемент разделения * /
last = left; / * к v [0] * /
for (i = left + 1; i <= right; i + +) / * поделить * /
if (v [i] swap (v, + + last, i);
swap (v, left, last) / * восстановить элемент разделения * /
qsort (v, left, last-1);
qsort (v, last +1, right);
}

Мы переместили операцию перестановка в отдельную функцию swap, поскольку она происходит три раза в qsort.
/ * Swap: поменять местами v [i] и v [j] * /
void swap (int v [], int i, int j)
{
int temp;

temp = v [i];
v [i] = v [j];
v [j] = temp;
}

Стандартная библиотека включает собственную версию qsort, способную сортировать объекты любого типа. Рекурсия может занимать место, так где-то нужно удерживать стек значений для обработки. Также она не является быстрой. Но рекурсивный код компактнее и часто намного проще в написании и понимании, чем не-рекурсивный эквивалент. Рекурсия особенно удобна для рекурсивно-определенных данных, например древовидных структур.

Другие статьи по теме:

- Типы, операторы и выражения
- Символьные массивы
- Внешние переменные и область действия
- Функции и структура программ
- Введение в c++

Другие голосования

Приглашаем Вас обменяться кнопочками! Обращайтесь к администратору.

• Как выбрать браузер
• Средства структурного анализа и проектирования систем
• Классификация case-средств
• Case-технология проектирования программного обеспечения информационных систем
• Технология intranet
• Технологии Internet
• Средства доступа к базам данных
• Средства быстрой разработки прикладных программ
• Объектно-ориентированный подход к созданию программных средств
• Этапы проектирования при разработке программного продукта