Алгоритмы и Структуры данных (Лабораторная работа №3)

Цель: Реализовать, протестировать и провести сравнительный анализ классических алгоритмов сортировки, а также ключевых структур данных (Стек, Очередь)

Описание: Данный проект содержит реализацию, тестирование и сравнительный анализ (бенчмарк) алгоритмов сортировки, а также реализацию двух основных структур данных: Стека и Очереди

Реализованные бонусы: CLI (Интерактивный режим), отчёт с бенчмарками

1) Установка проекта

Для начала работы необходимо клонировать репозиторий и установить зависимости в виртуальном окружении

git clone https://github.com/TheVailen/python-lab3-algopack 
cd python-lab3-algopack
python -m venv .venv
source .venv/bin/activate
pip install -e .

2) Реализованный функционал

Категория	Функции/Классы/Аргументы
Сортировки	bubble_sort
	quick_sort
	heap_sort
	counting_sort
	radix_sort
	bucket_sort
Структуры данных	Stack
	Queue
Математика	factorial
	fibo
Утилиты/Бонусы	benchmark
	--cli (Интерактивный режим)

3) Запуск программы и режимы работы

1. Полная демонстрация (Демо + Бенчмарк)

Программа поддерживает три режима запуска, используя аргументы командной строки (CLI)

Запуск по умолчанию, выполняет демонстрацию структур и запускает все бенчмарки:

python -m src.main

2. Интерактивный режим (CLI)

Запуск консоли для ручного тестирования любой реализованной функции (сортировки, факториал, Фибоначчи):

python -m src.main --cli

Примеры использования в интерактивном режиме:

--- Интерактивный режим (CLI). Введите 'exit' для выхода. ---
Доступные команды: bubble_sort, quick_sort, heap_sort, counting_sort, radix_sort, bucket_sort, factorial, fibo
> factorial 7
5040
> fibo 10
55
> quick_sort 5 1 4 2
[1, 2, 4, 5]
> bucket_sort 0.5 0.1 0.9 0.2
[0.1, 0.2, 0.5, 0.9]
> exit

3. Выборочный запуск

python -m src.main --demo        # Только демонстрация структур данных и математики
python -m src.main --benchmarks  # Только сравнительный анализ сортировок

Вывод бенчмарков:

--- БЕНЧМАРК 1: Сортировки целых чисел (N=1000) ---

Результаты Integer Benchmark (время в секундах):

Bubble Sort:
  Random Int: 0.016616
  Reversed Int: 0.020807

Quick Sort:
  Random Int: 0.000383
  Reversed Int: 0.012023

Heap Sort:
  Random Int: 0.000919
  Reversed Int: 0.000792

Counting Sort:
  Random Int: 0.000531
  Reversed Int: 0.000102

Radix Sort:
  Random Int: 0.000463
  Reversed Int: 0.000442

--- БЕНЧМАРК 2: Сортировки чисел Float [0, 1) (N=1000) ---

Результаты Float Benchmark (время в секундах):

Bucket Sort:
  Random Float [0, 1): 0.001535

Quick Sort (Float):
  Random Float [0, 1): 0.000369 

4) Тесты

pytest -v

5) Допущения

1. Counting Sort и Radix Sort работают только с неотрицательными целыми числами.

2. Bucket Sort работает только с числами float в диапазоне [0,1).

3. Максимальный лимит рекурсии (для Quick Sort) увеличен с помощью sys.setrecursionlimit.

4. В бенчмарках для сравнения с Bucket Sort используется Quick Sort как наиболее быстрый универсальный алгоритм.

6) Используемые библиотеки и модули

Категория	Модуль	Назначение
Системные	sys	Увеличение лимита рекурсии для предотвращения ошибок в Quick Sort и функциях Фибоначчи/Факториала
CLI	argparse	Создание интерфейса командной строки с поддержкой флагов (--cli, --benchmarks, --demo)
Данные	typing	Обеспечение строгой типизации (Dict, List, Callable) для улучшения читаемости и надежности кода
Бенчмарк	time	Точное измерение времени выполнения алгоритмов в секундах
Генерация	random	Генерация массивов случайных целых чисел и чисел с плавающей точкой для тестирования и бенчмаркинга

7) Чему я научился

1. Освоил реализацию и анализ сложности основных алгоритмов сортировки

2. Научился реализовывать структуры данных, такие как Стек и Очередь

3. Реализовал разработку тестового покрытия с использованием pytest и параметризации

4. Освоил технику бенчмаркинга для сравнения производительности алгоритмов на различных наборах входных данных

5. Реализовал интерфейс CLI с поддержкой интерактивного режима для тестирования