Главная /
Программирование /
Алгоритм быстрой сортировки использует вспомогательную функцию 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;
}
Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?
вопрос
Правильный ответ:
Реализация правильная.
Реализация неправильная.
Сложность вопроса
89
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
спасибо
08 фев 2020
Аноним
Экзамен сдал на пять.
26 фев 2016
Другие ответы на вопросы из темы программирование интуит.
- # Двоичный код, представляющий число типа double, хранит знак, смещенный порядок и дробную часть двоичного представления мантиссы. Сколько единичных битов в двоичном представлении дробной части мантиссы для числа 10.0?
- # Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия. При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче. Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл. Задание: удалить из массива все отрицательные значения, а оставшиеся уплотнить (сдвинуть) с сохранение исходного порядка к началу массива. Указать количество оставшихся значений.
- # Чему равно значение выражения (-17)%3*10 в языке C?
- # Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что значение переменной n неотрицательно. double r, x; int n; . . . r *= x*x; r /= ((n+1)*(n+2)); n += 2;
- # Пусть целочисленный массив содержит элементы 11, 18, 10, 7, 15, 9, 8 в указанном порядке. Услове пирамиды нарушается только для элемента 11, стоящего в вершине пирамиды. Для исправления пирамиды выполняется процедура просеивания, при которой элемент 11 опускается на свое место. Каким будет содержимое массива после окончания этой процедуры?