Главная /
Программирование /
Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл while; рекурсия применяется лишь к меньшему сегменту массива, разделенного на части функцией partition. void quickSort(double* a, int n) { if (n <= 1)
Алгоритм быстрой сортировки реализован с помощью комбинированной
схемы, использующей рекурсию и цикл while
;
рекурсия применяется лишь к меньшему сегменту массива,
разделенного на части функцией partition
.
void quickSort(double* a, int n) {
if (n <= 1) {
return;
} else if (n == 2) {
if (a[0] > a[1])
swap(&(a[0]), &(a[1]));
return;
}
int beg = 0;
int k = n;
while (k > 1) {
int m = k / 2;
partition(a+beg, k, &m);
int left = m;
int right = k - left - 1;
if (left <= right) {
// Рекурсивно применяем алг. к левой части
quickSort(a+beg, left);
beg += left + 1;
k -= left + 1;
} else {
// Рекурсивно применяем алг. к правой части
quickSort(a+beg+m+1, right);
k -= right + 1;
}
}
}
Алгоритм применяется к массиву размером 95. Какой может быть
максимальная глубина рекурсии?
(Под глубиной рекурсии мы подразумеваем количесто раз,
которое функция может вызвать сама себя в цепочке вызовов.
Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсии
нулевой.)
вопрос
Правильный ответ:
5
Сложность вопроса
63
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Я провалил сессию, какого рожна я не углядел этот сайт с решениями с тестами intuit в начале сессии
20 окт 2020
Аноним
Зачёт в студне отлично. Мчусь в клуб отмечать халяву с тестами интуит
27 мар 2020
Аноним
Это очень заурядный тест intuit.
10 фев 2019
Другие ответы на вопросы из темы программирование интуит.
- # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: посчитать количество чисел, больших предыдущего.
- # Каков диапазон целочисленного типа unsigned char?
- # В функции с прототипом int f(int x); которая вызывается часто в различных контекстах и должна работать быстро, нам требуется небольшой массив целых чисел размером в 16 элементов. Какое из перечисленных ниже решений является наиболее правильным?
- # Эквивалентны ли в языке C/C++ типы PntAct и VectAct, заданные в приведенном ниже фрагменте программы? typedef double R3Point[3]; typedef double R3Vector[3]; typedef void (*PntAct)(R3Point); typedef void (*VectAct)(R3Vector);
- # В массиве, содержащем 1000 элементов, выполняется последовательный поиск элемента x. При этом x содержится в массиве с вероятностью 0.75. Сколько в среднем операций сравнения будет выполнено?