Главная /
Программирование /
Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл 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;
}
}
}
Алгоритм применяется к массиву размером 191. Какой может быть
максимальная глубина рекурсии?
(Под глубиной рекурсии мы подразумеваем количесто раз,
которое функция может вызвать сама себя в цепочке вызовов.
Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсии
нулевой.)
вопрос
Правильный ответ:
6
Сложность вопроса
38
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Спасибо за ответы интуит
05 окт 2019
Аноним
Экзамен прошёл на 4 с минусом. лол
28 июл 2017
Другие ответы на вопросы из темы программирование интуит.
- # Пусть дан массив a длины n, элементы которого нестрого возрастают, т.е. соседние элементы могут быть равными. Рассмотрим фрагмент программы бинарного поиска элемента x в массиве a длины n, где после отбрасывания особых ситуаций рассматривается основной случай: . . . // Утверждение: a[0] < x && x <= a[n-1] int beg = 0; int end = n-1; while (end-beg > 1) { // Инвариант: a[beg] < x && x <= a[end] int c = (beg + end) / 2; if (a[c] < x) { beg = c; } else { end = c; } } *idx = end; . . . Пусть значение x содержится в массиве в нескольких экземплярах. Индекс какого элемента массива a будет записан в переменную *idx?
- # Массив длины 5 содержит элементы 2, 1, 5, 4, 3 в указанном порядке. К нему применяется алгоритм сортировки методом прямого выбора, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Сколько раз будет вызвана функция swap?
- # Алгоритм быстрой сортировки использует вспомогательную функцию partition, которая разделяет массив на 3 части: в начале элементы, меньшие либо равные медиане, затем медиана, в конце элементы, большие либо равные медиане. Рассмотрим следующую реализацию функции partition: void partition(double* a, int n, int *m) { if (*m != 0) // Ставим медиану в начало swap(&(a[0]), &(a[*m])); double x = a[0]; // Значение медианы int i = 0; int j = n; while (j-i > 1) { // Инв: a[1], a[2], ..., a[i] < x // a[j], a[j+1], ..., a[n-1] >= x if (a[i+1] < x) { ++i; } else if (a[j-1] >= x) --j; } else { ++i; --j; swap(&(a[i]), &(a[j])); } } if (i > 0) swap(&(a[0]), &(a[i])); *m = i; } Правильна ли подобная реализация, или она может привести к катастрофическому замедлению алгоритма быстрой сортировки в некоторых случаях?
- # Алгоритм быстрой сортировки упорядочивает случайный массив из тысячи элементов в среднем за 0.01 секунду. За какое примерно время тот же алгоритм упорядочит случайный массив из миллиона элементов?
- # Пусть целочисленный массив содержит элементы 10, 16, 12, 8, 11, 7, 5 в указанном порядке. Услове пирамиды нарушается только для элемента 10, стоящего в вершине пирамиды. Для исправления пирамиды выполняется процедура просеивания, при которой элемент 10 опускается на свое место. Каким будет содержимое массива после окончания этой процедуры?