Поиск медианы в массиве за O(N)

Медиа́на набора чисел — число, которое находится в середине этого набора, если его упорядочить по возрастанию, то есть такое число, что половина из элементов набора не меньше него, а другая половина не больше.

Например, медианой набора {11, 9, 3, 5, 5} является число 5, так как оно стоит в середине этого набора после его упорядочивания: {3, 5, 5, 9, 11}. Если в выборке чётное число элементов, медиана может быть не определена однозначно: тогда для числовых данных чаще всего используют полусумму двух соседних значений (то есть медиану набора {1, 3, 5, 7} принимают равной 4). В математической статистике медиана может использоваться как одна из характеристик выборки или совокупности чисел.

Нахождение медианы списка может казаться тривиальной задачей, но ее выполнение за линейное время требует серьезного подхода. Для этого используется алгоритм, который является частным случаем «quickselect», разработанного Тони Хоаром, который также изобрел алгоритм сортировки с похожим названием — quicksort. Это рекурсивный алгоритм, и он может находить любой элемент (не только медиану).

В среднем pivot разбивает список на две приблизительно равных части. Поэтому каждая последующая рекурсия оперирует с 1⁄2 данных предыдущего шага.

Команда "Fixiki"

Фамилия Имя	Вклад (%)	Прозвище
Видеева Ирина	49	Симка
Бадамшин Артур	49	Нолик
Сафин Рамиль	2	B0$$

Девиз команды «А кто такие фиксики — большой-большой секрет!»

Структура проекта

Описание основных частей семестрового проекта.

Проект состоит из следующих частей:

• src/include - реализация алгоритма (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных (поиск медианы);
• dataset - наборы данных для запуска контрольных тестов;

Требования (Prerequisites)

Рекомендуемые требования:

• 🔲 С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
• 🔲 Система автоматизации сборки CMake (версия 3.12.x и выше).
• 🔲 Java Development Kit (версия 8 и выше).
• 🔲 Рекомендуемый объем оперативной памяти - не менее 4 ГБ.
• 🔲 Свободное дисковое пространство объемом ~ 1 ГБ (набор данных для контрольных тестов).
• ✅ Желание

Сборка и запуск

Пример (Windows)

Сборка проекта

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-median.git

Для ручной сборки проекта в терминале введите:

# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-median

# создание папки для файлов сборки (чтобы не засорять папку с проектом) 
mkdir -p build && cd build 

# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . 

Генерация тестовых данных

Генерация тестового набора данных в формате comma-seperated values (CSV)

1. Склонируйте проект генератора набора случайных чисел ЗДЕСЬ к себе на устройство
2. Ознакомьтесь с инструкциями генерации
3. Сгенерируйте наборы данных

Контрольные тесты (benchmarks)

Тестирование:

1. Последовательно добавляются элементы из файла со сгенерированным набором данных
2. Засекается время
3. Выполняется алгоритм поиска медианы
4. Фиксируется время
5. Время записывается в файл-результат

Результаты наших тестов: ЗДЕСЬ

Список контрольных тестов

Название	Описание	Метрики
demo_benchmark.cpp	поиск медианы	время

Источники

• Статья на Хабре
• Видео на YouTube