Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется нисходящая (рекурсивная)схема...

Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется нисходящая (рекурсивная)схема реализации алгоритма. Алгоритм применяется к массивудлины 1000000 (миллион). Какова максимально возможнаяглубина рекурсии? Дайте наиболее точную оценку.

Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется восходящаясхема реализации алгоритма. Алгоритм применяется к массивудлины 100. На каждом шаге сливаются парысоседних упорядоченных подмассивов длиныне больше k и получаются упорядоченные подмассивыдлины не больше 2k; первый шаг выполняется приk=1.Сколько всего шагов будет выполнено?

Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл while;рекурсия применяется лишь к меньшему сегменту массива,разделенного на части функцией partition.Алгоритм применяется к массиву размером миллион. Может лиглубина рекурсии равняться 30?

Алгоритм сортировки называется стабильным, если онсохраняет относительный порядок равных элементов.Среди перечисленных ниже алгоритмов сортировки(имеются в виду их классические варианты) отметьте все стабильные.

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

Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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. Какой может бытьмаксимальная глубина рекурсии?(Под глубиной рекурсии мы подразумеваем количесто раз,которое функция может вызвать сама себя в цепочке вызовов.Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсиинулевой.)

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