Главная /
Программирование /
Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл while, а также вспомогательную функцию partition, которая разделяет текущий отрезок массива на 3 части (элементы, меньшие либо равные медиане, медиана, эл
Алгоритм быстрой сортировки реализован с помощью комбинированной
схемы, использующей рекурсию и цикл while
, а также
вспомогательную функцию partition,
которая разделяет текущий отрезок массива на 3 части
(элементы, меньшие либо равные медиане, медиана,
элементы, большие либо равные медиане):
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;
}
}
}
Сколько раз будет вызвана функция partition при выполнении
алгоритма быстрой сортировки для массива размера 95?
Дайте наиболее точную оценку снизу этого числа.
вопрос
Правильный ответ:
Не менее 5 раз.
Не менее 7 раз.
Не менее 15 раз.
Не менее 31 раза.
Сложность вопроса
41
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Я завалил зачёт, почему я не нашёл этот чёртов сайт с ответами с тестами intuit месяц назад
25 авг 2017
Аноним
Спасибо за сайт
26 июл 2017
Другие ответы на вопросы из темы программирование интуит.
- # Какая из конструкций цикла потенциально безопаснее?
- # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: найти величину максимального отклонения элементов последовательности от их среднего арифметического.
- # Какой объект описан в следующей строке программы на C/C++? double (*a)[20];
- # Рассмотрим следующую функцию, аргументами которой являются два целых неотрицательных числа: int f(int m, int n) { int a = m, b = n; int p = 0; while (b != 0) { if (b%2 == 0) { // b четное b /= 2; a *= 2; } else { // b нечетное --b; p += a; } } return p; } Какое условие является инвариантом цикла?
- # Алгоритм пузырьковой сортировки упорядочивает массив из 10 тысяч элементов примерно за 1 секунду. За какое примерно время тот же алгоритм упорядочит массив из 100 тысяч элементов?