Лабораторная работа 3

• Цель: Изучить структуры данных и сортировки

Допущения

• Алгоритмы(фибоначчи и факториала) рабутую корректно для ограничений заданных Python
• Алгоритмы сортировок все крому busket принимают тип int
• Для Radixsort принимаются неотрицательные числа
• Для Radixsort нужно дополнительно вводить основание системы счисления и возвращает массив в 10 сс
• стек сосздается автоматически и пользователь просто вводит команты без скобок
• написаны просто генераторы тестов. Они не интегрированы в программу

Чему я научился:

- Написание простых автотестов с помощью pytest
- Изучил несколько алгоратмивом сортировок
- Написал собственную структуру данных(Stack)
- Изучил рекурсивную и динамическую реализацию чисел фибоначи и факториала 
- Освоил модуль random для написания генераторов тестов 
- Некоторые азы OOП для написания стека 

Инструкции по запуску

Запуск программы

py -m src.main

Завершение выполнения

exit

Запуск тестов

python -m pytest tests/path -v для подробного вывода тестов python -m pytest tests/path для обычного запуска тестов

Команды

• bublesort - вызывает сортировку пузырьком
• countsort - вызывает сортировку подсчетом
• radixsort - вызывает поразрядную сортировку
• qsort - вызывает быструю сортировку
• bucketsort - вызывает блочную сортировку
• factorial - вызывает итеративную функцию вычисления факториала
• factorialrec - вызывает рекурсивную реализацию вычисления факториала
• fib - вызывает итеративную функцию вычисления числа фибоначчи
• fibrec - вызывает рекурсивную функцию вычисления чисел фибоначчи
• pop - извлекает послений элемент из стека и выводит в консоль
• peek - выводит последний элемент стека
• len - возвращает длину стека
• is_empty - проверяет пуст ли стек
• push - дабавить элемент в конец стека

Структуры Данных

Stack на листе

Стек — это абстрактный тип данных, представляющий собой коллекцию элементов, организованных по принципу LIFO (Last In, First Out) — последним пришел, первым вышел.

Методы Stack

1. init()- инициализация стека
2. push(self, item) - добавления элементка в конец
3. empty(self)- проверка на пнстоту
4. pop(self) - удаление и возврат последнего эдемента
5. peek(self) - возвращает последний элемент без удаления
6. len(self) - возвращает количество элементов в списке

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

1. rand_int_array Генерирует массив случайных целых чисел в заданном диапазоне
2. nearly_sorted - Генерирует почти отсортированный массив
3. many_duplicates - Генерирует массив с большим количеством дубликатов
4. reverse_sorted - Генерирует обратно отсортированный массив
5. rand_float_array - Генерирует массив случайных вещественных чисел в заданном диапазоне

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

Сортировка Пузырьком (Bubble Sort)

Принцип работы:

1. Проход по массиву от начала до конца
2. Сравнение соседних элементов на каждой итерации
3. Обмен элементов при неправильном порядке расположения
4. Повторение процесса до полной сортировки массива
5. Оптимизация: флаг для досрочного завершения при отсутствии обменов

Быстрая Сортировка (Quick Sort)

Принцип работы:

1. Выбор опорного элемента (pivot) из массива
2. Разделение массива на три части:
   • Элементы меньше опорного
   • Элементы равные опорному
   • Элементы больше опорного
3. Рекурсивная сортировка левой и правой частей
4. Объединение отсортированных частей

Сортировка Подсчетом (Count Sort)

Принцип работы

1. Определение диапазона — нахождение минимального и максимального значений
2. Создание массива подсчета — инициализация массива для подсчета частот
3. Подсчет элементов — заполнение массива частотами встречаемости
4. Накопительный подсчет — преобразование частот в позиции
5. Построение отсортированного массива — размещение элементов в правильном порядке

Поразрядная сортировка (Radix Sort)

Принцип работы

1. Определение максимального числа — нахождение самого большого числа в массиве
2. Вычисление количества разрядов — определение сколько разрядов нужно обработать
3. Последовательная обработка разрядов — от младшего к старшему
4. Распределение по корзинам — для каждого разряда числа распределяются по "корзинам" соответствующим цифрам
5. Сборка массива — числа собираются из корзин в порядке возрастания цифр
6. Повторение — процесс повторяется для всех значимых разрядов

Блочная сортировка (Busket Sort)

Принцип работы

1. Создаем n пустых корзин
2. Для каждого элемента вычисляем индекс корзины и распределяем по карзинам
3. Каждую непустую корзину сортируем отдельно
4. Объединяем отсортированные корзины в результирующий массив

Heap Sort

Принцип работы

1. Инициализация корня
2. Сравнение с правым и левым узлами
3. Если наибольший не равен корню то меняем
4. Восстанавливаем пирамиду