Расчетно-графическая работа. Структуры и алгоритмы обработки данных. 2020

Расчетно-графическая работа. Структуры и алгоритмы обработки данных. 2020

Постановка задачи
Задана последовательность из n элементов. Найти медиану для этих n элементов. Медианой для n элементов называется элемент, меньший (или равный) половине из n элементов и больший (равный) другой половине из n элементов.

Алгоритм нахождения медианы
Данную проблему можем решить с помощью алгоритма нахождения k й порядковой статистики. Так как нужно найти медиану, то k = n / 2.
Выбирается опорный элемент – центр текущей последовательности. Последовательность разбивается на две части относительно опорного элемента – в одну часть попадают элементы, меньшие, чем выбранного, в другую – остальные. По окончании опорный элемент окажется на j позиции.
Если в первой части оказалось j=k-1 элементов, то выбранный центральный элемент является искомым, если j>k, то алгоритм выполняется рекурсивно для первой части массива, иначе – для второй.
1. Вводим число n – количество элементов последовательности.
2. Генерируется массив значений размерности n.
3. Задаем индекс k-й статистики = n / 2, т.е. номер середины массива.
4. Задаем индекс левой и правой границы массива.
5. Пока индекс левой границы меньше правой
5.1. Задаем опорный элемент равной значению центра массива.
5.2. Задаем i равной левой границе.
5.3. Задаем j равной правой границе.
5.4. Пока i<=j
5.4.1. Пока значение i элемента меньше опорного,
то увеличиваем i на единицу.
5.4.2. Пока значение j элемента больше опорного,
то уменьшаем j на единицу.
5.4.3. Если i<=j, то
5.4.3.1. Меняем местами i и j элементы.
5.4.3.2. Увеличиваем i на единицу.
5.4.3.3. Уменьшаем j на единицу.
5.5. Если j<k,
То левая граница = i
5.6. Если i>k,
То правая граница = j
6. Вывод центрального элемента массива.




Входные данные:
• array - массив элементов последовательности
• n – количество элементов последовательности.

Выходные данные
• result – значение медианы последовательности.

2020