Главная /
Программирование /
Алгоритм быстрой сортировки использует вспомогательную функцию partition, которая разделяет массив на 3 части: в начале элементы, меньшие либо равные медиане, затем медиана, в конце элементы, большие либо равные медиане. Рассмотрим следующую реализацию фу
Алгоритм быстрой сортировки использует вспомогательную функцию
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;
}
Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?
вопрос
Правильный ответ:
Реализация правильная.
Реализация неправильная.
Сложность вопроса
93
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Если бы не опубликованные решения - я бы не осилил c этими тестами интуит.
15 дек 2017
Аноним
Пишет вам помощник профессора! Тотчас уничтожьте сайт с ответами с интуит. Не ломайте образование
14 янв 2016
Другие ответы на вопросы из темы программирование интуит.
- # При представлении целых чисел в формате Big Endian байты внутри слова нумеруются слева направо, в формате Little Endian - справа налево. Пусть компьютер использует архитектуру Big Endian. Укажите, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int k = (-256); int n; signed char *p = (signed char *) &k; n = *p;
- # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: определить порядковый номер первого числа, равного максимуму по всей последовательности.
- # Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что n не меньше k. Восклицательным знаком обозначается операция вычисления факториала. int n, k, c; . . . c *= (n+1); c /= (n+1-k); ++n;
- # Пусть элементы массива a нестрого возрастают (соседние элементы могут быть равными). Дано произвольное значение x, требуется найти максимальный индекс i такой, что a[i] <= x. Используется идея алгоритма бинарного поиска. Каким должен быть инвариант цикла, в котором рассматривается основной случай после отбрасывания исключительных ситуаций? (Условие завершения цикла end == beg+1.)
- # Массив длины 5 содержит элементы 2, 1, 5, 4, 3 в указанном порядке. К нему применяется алгоритм сортировки методом прямого выбора, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Сколько раз будет вызвана функция swap?