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

Упражнение 1:

Номер 1

Алгоритм быстрой сортировки использует вспомогательную функцию
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;
}

Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?

Ответ:

(1) Реализация правильная.

(2) Реализация неправильная.

Номер 2

Алгоритм быстрой сортировки использует вспомогательную функцию
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;
}

Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?

Ответ:

(1) Реализация правильная.

(2) Реализация неправильная.

Упражнение 2:

Номер 1

Алгоритм быстрой сортировки использует вспомогательную функцию
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;
}

Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?

Ответ:

(1) Реализация правильная.

(2) Реализация неправильная.

Номер 2

Алгоритм сортировки называется стабильным,
если он сохраняет взаимный порядок равных элементов.
(Такое определение имеет смысл при сортировке массива записей,
состоящих из нескольких полей, которые сравниваются лишь
по значению одного конкретного поля - например, записи о людях
сортируются по их именам, при этом могут быть однофамильцы.)
Является ли алгоритм быстрой сортировки стабильным?

Ответ:

(1) Да.

(2) Нет.

Упражнение 3:

Номер 1

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

Ответ:

(1) Не менее 4 раз.

(2) Не менее 7 раз.

(3) Не менее 15 раз.

(4) Не менее 31 раза.

Номер 2

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

Ответ:

(1) Не менее 5 раз.

(2) Не менее 7 раз.

(3) Не менее 15 раз.

(4) Не менее 31 раза.

Упражнение 4:

Номер 1

Алгоритм быстрой сортировки упорядочивает случайный массив
из 128 элементов в среднем за 0.0001 секунду. За какое примерно
время тот же алгоритм упорядочит случайный массив
из 1024 элементов?

Ответ:

(1) За 0.0011 секунды.

(2) За 0.0023 секунды.

(3) За 0.0054 секунды

(4) За 0.0075 секунды

(5) За 0.0099 секунды

Номер 2

Алгоритм быстрой сортировки упорядочивает случайный массив
из тысячи элементов в среднем за 0.01 секунду. За какое примерно
время тот же алгоритм упорядочит случайный массив
из миллиона элементов?

Ответ:

(1) За 10 секунд

(2) За 20 секунд

(3) За 1 минуту 40 секунд

(4) За 30 секунд

(5) За 1 минуту 20 секунд

Упражнение 5:

Номер 1

Алгоритм быстрой сортировки упорядочивает случайный массив
из миллиона элементов в среднем за 40 секунд. За какое примерно
время тот же алгоритм упорядочит случайный массив
из тысячи элементов?

Ответ:

(1) За 0.01 секунды.

(2) За 0.02 секунды.

(3) За 0.04 секунды.

(4) За 0.1 секунды.

Номер 2

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

Ответ:

(1) Может.

(2) Не может.

Упражнение 6:

Номер 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

Номер 2

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

Программирование - тест 88