как блок. Напишите функцию bucketSort, которая принимает массив целых чисел и его размер как аргументы и выполняет следую-ш;ее:

1) Поместите каждое значение одномерного массива в строку массива блоков, основываясь на значении его первого разряда. Например, 97 помеш;ается в строку 7, 3 помеш;ается в строку 3, а 100 помеш;ается в строку 0. Это называется распределяюш;ий проход .

2) Циклически обработайте массив блоков строка за строкой и скопируйте значения обратно в исходный массив. Это называется со-бираюпций проход . Новый порядок предыдущих значений в одномерном массиве будет 100, 3 и 97.

3) Повторите этот процесс для каждого последовательного разряда (десятки, сотни, тысячи и тому подобное).

На втором проходе 100 разместится в строке О, 3 разместится в строке О (потому что 3 не имеет разряда десятков), а 97 разместится в строке 9. На третьем проходе 100 поместится в строке!, 3 поместится в нулевой строке и 97 поместится в нулевой строке (после цифры 3). После последнего собирающего прохода исходный массив будет отсортирован.

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

Упражнения на рекурсию

4.31. (Сортировка отбором). Сортировка отбором анализирует массив, отыскивая наименьший элемент массива. Затем этот наименьший элемент обменивается местами с первым элементом массива. Процесс повторяется для подмассива, начинающегося со второго элемента массива. В результате каждого прохода один из элементов занимает соответствующее место. Эта сортировка по производительности сравнима с пузырьковой - для массива из п элементов нужно выполнить п - 1 проход, а для каждого подмассива нужно выполнить п - 1 сравнение для определения наименьшего значения. Когда обрабатываемый подмассив будет содержать только один элемент, значит массив отсортирован. Напишите рекурсивную функцию selec-tionSort, выполняющую этот алгоритм.

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

4.33. (Линейный поиск) Модифицируйте программу на рис. 4.19 так, чтобы использовать рекурсивную функцию linearSeach для линейного поиска в массиве. Функция должна принимать массив целых чисел и размер массива как аргументы. Если ключ поиска найден, верните индекс массива, в противном случае верните -1.

4.34. (Двоичный поиск) Модифицируйте программу на рис. 4.19 так, чтобы использовать рекурсивную функцию binarySearch для двоичного поиска в массиве. Функция должна принимать массив целых чисел и начальный и конечный индексы как аргументы. Если ключ поиска найден, верните индекс массива, в противном случае верните -1.

4.35. (Восемь Ферзей) Модифицируйте программу Восемь Ферзей, которую вы создали в упражнении 4.26, для рекурсивного решения задачи.

4.36. (Печать массива) Напишите рекурсивную функцию printArray, которая принимает массив и размер массива как аргументы и ничего не возвраш;ает. Функция должна прекращать свою работу и возвращаться, если принимаемый массив имеет нулевой размер.

4.37. (Печать строки в обратном направлении) Напишите рекурсивную функцию stringReverse, которая принимает символьный массив, содержащий строку, как аргумент, печатает строку в обратном направлении и ничего не возвращает. Функция должна прекращать свою работу и возвращаться, если обнаружен завершающий нулевой символ.

4.38. (Поиск минимального значения в массиве) Напишите рекурсивную функцию recursiveMinimum, которая принимает массив и размер массива как аргументы и возвращает наименьший элемент массива. Функция должна прекращать свою работу и возвращаться, если принимаемый массив имеет один элемент.

глава

Указатели и строки

Цели

Научиться использовать указатели.

Научиться использовать указатели для передачи аргументов в функции по ссылке.

Понять тесную взаимосвязь между указателями, массивами и строками.

Понять, как использовать указатели на функции.

Научиться объявлять и использовать массивы строк.