База ответов ИНТУИТ

Программирование

<<- Назад к вопросам

Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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 при выполненииалгоритма быстрой сортировки для массива размера 47?Дайте наиболее точную оценку снизу этого числа.

(Отметьте один правильный вариант ответа.)

Варианты ответа
Не менее 31 раза.
Не менее 4 раз.
Не менее 7 раз.
Не менее 15 раз. (Верный ответ)
Похожие вопросы
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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?Дайте наиболее точную оценку снизу этого числа.
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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. Какой может бытьмаксимальная глубина рекурсии?(Под глубиной рекурсии мы подразумеваем количесто раз,которое функция может вызвать сама себя в цепочке вызовов.Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсиинулевой.)
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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. Какой может бытьмаксимальная глубина рекурсии?(Под глубиной рекурсии мы подразумеваем количесто раз,которое функция может вызвать сама себя в цепочке вызовов.Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсиинулевой.)
Алгоритм быстрой сортировки использует вспомогательную функцию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;}
Правильна ли подобная реализация, или она может привестик катастрофическому замедлению алгоритма быстройсортировки в некоторых случаях?
Алгоритм быстрой сортировки использует вспомогательную функцию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;}
Правильна ли подобная реализация, или она может привестик катастрофическому замедлению алгоритма быстройсортировки в некоторых случаях?
Алгоритм быстрой сортировки использует вспомогательную функцию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;}
Правильна ли подобная реализация, или она может привестик катастрофическому замедлению алгоритма быстройсортировки в некоторых случаях?
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл while;рекурсия применяется лишь к меньшему сегменту массива,разделенного на части функцией partition.Алгоритм применяется к массиву размером миллион. Может лиглубина рекурсии равняться 30?
Массив a размера 4 содержитэлементы 4, 2, 1, 3 в указанном порядке.К нему применяется алгоритм пузырьковой сортировки,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Массив a размера 4 содержитэлементы 4, 3, 2, 1 в указанном порядке.К нему применяется алгоритм пузырьковой сортировки,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Массив a размера 4 содержитэлементы 4, 1, 3, 2 в указанном порядке.К нему применяется алгоритм пузырьковой сортировки,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?