Главная /
Программирование /
Алгоритм быстрой сортировки использует вспомогательную функцию 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;
}
Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?
вопрос
Правильный ответ:
Реализация правильная.
Реализация неправильная.
Сложность вопроса
62
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Экзамен сдан на пять. Спасибо vtone
25 июн 2020
Аноним
Если бы не данные решения - я бы сломался c этими тестами интуит.
22 июн 2018
Другие ответы на вопросы из темы программирование интуит.
- # Для записи n-значных чисел в системе счисления с основанием b требуется n разрядов, каждый из которых может находиться в b состояниях. Таким образом, суммарное число состояний равно произведению n*b. Рассмотрим двоичную (b=2), восьмеричную (b=8) и шестнадцатеричную (b=16) системы счисления. Какая из них наиболее экономна по суммарному числу состояний для записи чисел в диапазоне 0..N, где N - некоторое достаточно большое число?
- # Двоичный код, представляющий число типа double, хранит знак, смещенный порядок и дробную часть двоичного представления мантиссы. Сколько битов отводится под каждый элемент представления?
- # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: найти количество элементов в наибольшем постоянном участке последовательности целых чисел.
- # Пусть переменные p, q описаны следующим образом: double *p, q[100]; Отметьте, какие из перечисленных ниже выражений языка C/C++ являются корректными:
- # Какие смещения относительно регистра FP (Frame Pointer - указатель кадра) имеют адреса локальных переменных, описанных внутри функции, в языке C/C++?