Лабораторная работа №3: Алгоритмический мини-пакет

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

├── src/
│ ├── benchmark/
│ │ └── benchmark.py
│ ├── data_structures/
│ │ ├── queue_structure.py
│ │ └── stack_structure.py
│ ├── functions/
│ │ ├── factorial.py
│ │ └── fibo.py
│ ├── generators/
│ │ └── array_generators.py
│ ├── sorting/
│ │ ├── bubble_sort.py
│ │ ├── bucket_sort.py
│ │ ├── counting_sort.py
│ │ ├── heap_sort.py
│ │ ├── quick_sort.py
│ │ └── radix_sort.py
│ └── main.py
├── tests/
│ └── tests.py
├── .gitignore  
├── .pre-commit-config.yaml
├── pyproject.toml
├── README.md
├── requirements.txt
└── uv.lock

Функциональность

1. Математические функции

• Факториал: итеративная и рекурсивная реализации
• Числа Фибоначчи: итеративная и рекурсивная реализации

2. Алгоритмы сортировки

• Bubble Sort - пузырьковая сортировка с двунаправленным проходом
• Quick Sort - быстрая сортировка с опорным элементом из середины
• Heap Sort - пирамидальная сортировка
• Counting Sort - сортировка подсчетом для целых чисел
• Radix Sort - поразрядная сортировка для целых чисел
• Bucket Sort - блочная сортировка для вещественных чисел

3. Структуры данных

• Stack - стек на основе списка
• Queue - очередь на основе списка

4. Генераторы массивов

• Случайные целочисленные массивы
• Почти отсортированные массивы
• Массивы с дубликатами
• Обратно отсортированные массивы
• Случайные вещественные массивы

5. Бенчмаркинг

• Измерение времени выполнения функций
• Сравнительный анализ алгоритмов сортировки

Бенчмарк алгоритмов сортировки (1000 элементов, ms)

Algorithm	random 1k	reversed 1k	nearly sorted 1k	duplicates 1k	random float 1k
Bubble	27.483933	46.269733	1.438900	26.136933	27.685100
Quick	1.255767	0.701167	0.740933	0.200133	1.147167
Heap	1.851233	1.907367	1.837633	1.400300	1.771167
Radix	0.540700	0.415733	0.296467	0.324100	0.063300
Counting	0.255500	0.232567	0.212400	0.198400	Ошибка
Bucket	2.291233	2.517867	0.590867	0.516067	1.245567

Клонирование репозитория

git clone https://github.com/plll666/lab3

Использование в интерактивном режиму

python src/main.py interactive

Доступные команды

• sort <algorithm> <numbers...> - сортировка чисел
• struct <name> <operation> [values] - работа со структурами данных
• func <name> <number> - вычисление математических функций

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

pytest tests/tests.py

Установка зависимостей

pip install -r requirements.txt