Differences

This shows you the differences between two versions of the page.

--- g3l:lab3_var1 [2026/02/25 09:54] – created - external edit 127.0.0.1
+++ g3l:lab3_var1 [2026/02/25 10:00] (current) – eugeneai
@@ Line 1: / Line 1: @@
-====== Сортировка пузырьком с визуализацией ======
+====== Лабораторная работа 3.1: Алгоритмы сортировки с визуализацией ======
-**Задание:** Реализовать сортировку пузырьком с визуализацией процесса сортировки
+===== Общие требования =====
+  * Язык программирования: любой (C++, Python, Java, C#)
+  * Визуализация процесса сортировки обязательна
+  * Программа должна показывать каждый шаг/проход алгоритма
+  * Входные данные: массив из 10-15 элементов (целые числа)
+  * Выходные данные: пошаговый вывод процесса сортировки + итоговый массив
-**Пример входных данных:**
+===== Вариант 1: Пузырьковая сортировка (Bubble Sort) с пошаговым выводом =====
-<code>
+**Тип сортировки:** Внутренняя, обменная
-f(x) = e^x - 3x = 0
-Начальное приближение: x0 = 1.0
-Точность: 0.0001
-</code>
+**Задание:** Реализовать классическую сортировку пузырьком. На каждом проходе выводить текущее состояние массива и выделять сравниваемые элементы.
-**Пример выходных данных:**
+**Требования к визуализации:**
+  * После каждого прохода выводить строку: "Проход X: [массив]"
+  * Сравниваемые пары выделять скобками: (a b)
+  * Обмены помечать символом "<->"
-<code>
+**Пример вывода:**
-Корень уравнения: x = 1.5121
+  Исходный массив: [5, 1, 4, 2, 8]
-Количество итераций: 5
-f(1.5121) = 0.00008
+  Проход 1:
+    Сравнение (5 1): 1 <-> 5 -> [1, 5, 4, 2, 8]
+    Сравнение (5 4): 4 <-> 5 -> [1, 4, 5, 2, 8]
+    Сравнение (5 2): 2 <-> 5 -> [1, 4, 2, 5, 8]
+    Сравнение (5 8): обмена нет
+  Результат прохода 1: [1, 4, 2, 5, 8]
+  Проход 2:
+    ...
+  Отсортированный массив: [1, 2, 4, 5, 8]
-</code>
+===== Вариант 2: Сортировка вставками (Insertion Sort) с гистограммой =====
+**Тип сортировки:** Внутренняя, вставками
+**Задание:** Реализовать сортировку вставками. Визуализировать процесс с помощью ASCII-гистограммы.
+**Требования к визуализации:**
+  * Каждый элемент отображается как столбец из символов '#'
+  * Высота столбца пропорциональна значению элемента
+  * Текущий вставляемый элемент выделять цветом/символом '*'
+  * Отсортированную часть отделять вертикальной чертой '|'
+**Пример вывода:**
+  Шаг 1: Вставляем 4
+  [###] | [#] [#####] [##]
+     1     5     2
+  Шаг 2: Вставляем 5
+  [#] [###] | [#####] [##]
+    3       5     2
+===== Вариант 3: Сортировка выбором (Selection Sort) с анимацией в консоли =====
+**Тип сортировки:** Внутренняя, выбором
+**Задание:** Реализовать сортировку выбором. Создать эффект анимации в консоли (очистка экрана и перерисовка).
+**Требования к визуализации:**
+  * Использовать модули времени (sleep) и очистки экрана (clear/cls)
+  * Показывать поиск минимального элемента
+  * Найденный минимум и текущую позицию для обмена выделять разными цветами
+  * Выводить счетчик сравнений
+**Пример вывода (кадры анимации):**
+  [5] {1} [4] [2] [8]  (Поиск минимума: {1} - кандидат)
+  [5] [1] [4] {2} [8]  (Найден новый минимум {2})
+  Обмен: [1] <-> [5]
+  [1] [5] [4] [2] [8]  (После обмена)
+===== Вариант 4: Быстрая сортировка (Quick Sort) с рекурсивным деревом =====
+**Тип сортировки:** Внутренняя, рекурсивная
+**Задание:** Реализовать быструю сортировку (алгоритм Хоара). Визуализировать процесс в виде дерева рекурсии.
+**Требования к визуализации:**
+  * Показывать выбор опорного элемента (Pivot)
+  * Отображать разделение массива на левую и правую части
+  * Выводить отступами уровень рекурсии
+  * После каждой рекурсии показывать объединенный результат
+**Пример вывода:**
+  Уровень 0: [5, 1, 4, 2, 8] (pivot=5)
+    Левая часть: [1, 4, 2]
+      Уровень 1: [1, 4, 2] (pivot=1)
+        Левая часть: [] (пусто)
+        Правая часть: [4, 2]
+          Уровень 2: [4, 2] (pivot=4)
+            Левая часть: [2]
+            Правая часть: []
+          Возврат: [2, 4]
+      Возврат: [1, 2, 4]
+    Правая часть: [8]
+  Возврат: [1, 2, 4, 5, 8]
+===== Вариант 5: Сортировка слиянием (Merge Sort) с визуализацией слияний =====
+**Тип сортировки:** Внешняя/внутренняя, рекурсивная
+**Задание:** Реализовать сортировку слиянием. Показать процесс разделения и слияния массивов.
+**Требования к визуализации:**
+  * Показывать разделение массива на две половины (стрелками вниз)
+  * Показывать процесс слияния (стрелками вверх)
+  * При слиянии выводить сравниваемые элементы из двух половин
+  * Использовать квадратные скобки для отслеживания указателей
+**Пример вывода:**
+  Делим: [5, 1, 4, 2, 8]
+         /            \
+    [5, 1, 4]       [2, 8]
+     /     \        /    \
+  [5]     [1,4]    [2]   [8]
+          /  \
+        [1]  [4]
+  Сливаем:
+    Слияние [1] и [4] -> [1, 4]
+    Слияние [5] и [1, 4] -> сравниваем 5 и 1, берем 1; сравниваем 5 и 4, берем 4; берем 5 -> [1, 4, 5]
+    Слияние [2] и [8] -> [2, 8]
+    Слияние [1, 4, 5] и [2, 8] -> [1, 2, 4, 5, 8]
+===== Вариант 6: Шейкерная сортировка (Cocktail Shaker Sort) с направлением =====
+**Тип сортировки:** Внутренняя, обменная
+**Задание:** Реализовать двунаправленную пузырьковую сортировку. Визуализировать направление движения.
+**Требования к визуализации:**
+  * Использовать стрелки для показа направления прохода (→ и ←)
+  * После каждого прохода показывать границы отсортированной части
+  * Выводить текущее положение "шейкера"
+**Пример вывода:**
+  Исходный: [5, 1, 4, 2, 8]
+  Проход → (0→3):
+    [1, 5, 4, 2, 8] (обмен 5 и 1)
+    [1, 4, 5, 2, 8] (обмен 5 и 4)
+    [1, 4, 2, 5, 8] (обмен 5 и 2)
+  Результат: [1, 4, 2, 5, 8]
+  Проход ← (3→1):
+    [1, 4, 2, 5, 8] ←
+    [1, 2, 4, 5, 8] (обмен 4 и 2 на позициях 1-2)
+  Результат: [1, 2, 4, 5, 8]
+===== Вариант 7: Сортировка Шелла (Shell Sort) с визуализацией шагов =====
+**Тип сортировки:** Внутренняя, вставками с шагом
+**Задание:** Реализовать сортировку Шелла. Показать влияние выбора шага (последовательность Шелла: N/2, N/4, ..., 1).
+**Требования к визуализации:**
+  * Для каждого шага показывать, какие элементы сравниваются (разноцветное выделение)
+  * Выводить значение текущего шага (gap)
+  * Показывать подмассивы, которые сортируются отдельно
+**Пример вывода:**
+  Массив: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
+  Шаг 1: gap = 5
+    Сортируем подмассивы:
+    [9, 4] -> [4, 9]  (индексы 0 и 5)
+    [8, 3] -> [3, 8]  (индексы 1 и 6)
+    [7, 2] -> [2, 7]  (индексы 2 и 7)
+    [6, 1] -> [1, 6]  (индексы 3 и 8)
+    [5, 0] -> [0, 5]  (индексы 4 и 9)
+  После шага 1: [4, 3, 2, 1, 0, 9, 8, 7, 6, 5]
+===== Вариант 8: Сортировка подсчетом (Counting Sort) с частотным словарем =====
+**Тип сортировки:** Внутренняя, не сравнительная
+**Задание:** Реализовать сортировку подсчетом для чисел в небольшом диапазоне (0-20). Визуализировать подсчет частот.
+**Требования к визуализации:**
+  * Показать процесс подсчета количества вхождений каждого числа
+  * Визуализировать массив счетчиков в виде гистограммы
+  * Показать восстановление отсортированного массива
+**Пример вывода:**
+  Исходный массив: [4, 2, 2, 8, 3, 3, 1]
+  Подсчет частот:
+  Значение: 0 1 2 3 4 5 6 7 8
+  Счетчик: [0,1,2,2,1,0,0,0,1]
+  Визуализация счетчиков:
+: ##
+: ##
+: #
+: #
+: #
+  Восстановление:
+    Берем 1 (1 раз): [1]
+    Берем 2 (2 раза): [1, 2, 2]
+    Берем 3 (2 раза): [1, 2, 2, 3, 3]
+    Берем 4 (1 раз): [1, 2, 2, 3, 3, 4]
+    Берем 8 (1 раз): [1, 2, 2, 3, 3, 4, 8]
+===== Вариант 9: Поразрядная сортировка (Radix Sort) с разрядами =====
+**Тип сортировки:** Внутренняя, цифровая
+**Задание:** Реализовать поразрядную сортировку (LSD - от младшего разряда к старшему). Визуализировать сортировку по каждому разряду.
+**Требования к визуализации:**
+  * Показывать текущий разряд (единицы, десятки, сотни)
+  * Визуализировать распределение по корзинам (0-9)
+  * Показывать сборку массива после каждого разряда
+**Пример вывода:**
+  Массив: [170, 45, 75, 90, 2, 24, 802, 66]
+  Разряд 1 (единицы):
+    Распределение по корзинам:
+: [170, 90]
+: [2, 802]
+: [24]
+: [45, 75]
+: [66]
+    Сборка: [170, 90, 2, 802, 24, 45, 75, 66]
+  Разряд 2 (десятки):
+    Распределение по корзинам:
+: [2, 802]
+: [24]
+: [45]
+: [66]
+: [170, 75]
+: [90]
+    Сборка: [2, 802, 24, 45, 66, 170, 75, 90]
+===== Вариант 10: Пирамидальная сортировка (Heap Sort) с визуализацией кучи =====
+**Тип сортировки:** Внутренняя, пирамидальная
+**Задание:** Реализовать пирамидальную сортировку. Визуализировать построение max-кучи и процесс извлечения элементов.
+**Требования к визуализации:**
+  * Показывать бинарное дерево в текстовом виде
+  * Выделять текущую "просеиваемую" вершину
+  * Показывать обмен корня с последним элементом
+**Пример вывода:**
+  Построение кучи:
+       / \
+   4
+     / \
+   8
+  Просеиваем 5:
+       / \
+   4
+     / \
+   1
+  Сортировка:
+    Корень=8, меняем с последним=1
+       / \
+   4
+     /
+    Просеиваем 1:
+       / \
+   4
+     /
+    ...
+===== Вариант 11: Сортировка бинарным деревом (Binary Tree Sort) с графическим выводом =====
+**Тип сортировки:** Внешняя (структура данных - дерево)
+**Задание:** Реализовать сортировку с помощью бинарного дерева поиска. Визуализировать построение дерева.
+**Требования к визуализации:**
+  * Показывать вставку каждого элемента в дерево
+  * Отображать дерево с отступами (правые поддеревья с большим отступом)
+  * Показать симметричный обход (in-order traversal) для получения отсортированного массива
+**Пример вывода:**
+  Вставляем 5:
+  Вставляем 3:
+   /
+  Вставляем 7:
+   / \
+   7
+  Вставляем 2:
+     / \
+   7
+   /
+  Обход (in-order): 2, 3, 5, 7
+===== Вариант 12: Гномья сортировка (Gnome Sort) с "шагами гнома" =====
+**Тип сортировки:** Внутренняя, обменная
+**Задание:** Реализовать гномью сортировку. Визуализировать перемещение "гнома" по массиву.
+**Требования к визуализации:**
+  * Позицию гнома отмечать символом '@'
+  * Показывать движение вперед (→) и назад (←)
+  * Выводить каждое перемещение гнома
+**Пример вывода:**
+  [@5, 1, 4, 2, 8] (начало)
+  [5, @1, 4, 2, 8] (шаг вперед, 5>1 - меняем)
+  [1, @5, 4, 2, 8] (шаг назад, сравниваем 1 и 5 - порядок норм)
+  [1, 5, @4, 2, 8] (шаг вперед, 5>4 - меняем)
+  [1, @4, 5, 2, 8] (шаг назад, 1<4 - норм, шаг вперед)
+  [1, 4, @5, 2, 8] (5>2 - меняем)
+  [1, 4, 2, @5, 8] (шаг назад, 4>2 - меняем)
+  [1, 2, 4, @5, 8] (шаг назад, 1<2 - норм, вперед до конца)
+===== Вариант 13: Сортировка расческой (Comb Sort) с визуализацией фактора =====
+**Тип сортировки:** Внутренняя, обменная
+**Задание:** Реализовать сортировку расческой (улучшенный пузырек с уменьшающимся шагом). Визуализировать влияние фактора уменьшения.
+**Требования к визуализации:**
+  * Показывать текущий шаг (gap)
+  * Сравниваемые элементы соединять линией в выводе
+  * Показывать уменьшение шага
+**Пример вывода:**
+  Массив: [8, 4, 1, 5, 9, 2, 7, 3]
+  Фактор: 1.247
+  Шаг 1: gap = 8 → 6
+    [8]----[2] → 8>2, меняем: [2, 4, 1, 5, 9, 8, 7, 3]
+    [4]----[7] → 4<7, без обмена
+    [1]----[3] → 1<3, без обмена
+  Шаг 2: gap = 6 → 4
+    [2]----[9] → 2<9, без обмена
+    ...
+===== Вариант 14: Сортировка перемешиванием (Odd-Even Sort) с параллельными сравнениями =====
+**Тип сортировки:** Внутренняя, параллельная
+**Задание:** Реализовать сортировку чет-нечет (Odd-Even Transposition Sort). Визуализировать фазы четных и нечетных сравнений.
+**Требования к визуализации:**
+  * Четную фазу выделять одним цветом, нечетную - другим
+  * Показывать все сравнения в фазе одновременно (как при параллельной работе)
+  * Выводить номер итерации и фазы
+**Пример вывода:**
+  Итерация 1:
+    Фаза 1 (четные индексы 0,2,4):
+      Сравниваем (0,1): [5,1] → [1,5]
+      Сравниваем (2,3): [4,2] → [2,4]
+      Сравниваем (4,5): [8,?] - нет пары
+      Результат: [1, 5, 2, 4, 8]
+    Фаза 2 (нечетные индексы 1,3):
+      Сравниваем (1,2): [5,2] → [2,5]
+      Сравниваем (3,4): [4,8] → без обмена
+      Результат: [1, 2, 5, 4, 8]
+===== Вариант 15: Timsort (гибрид сортировки вставками и слиянием) с определением RUN =====
+**Тип сортировки:** Внутренняя, гибридная
+**Задание:** Реализовать упрощенный Timsort (разбиение на RUN и слияние). Визуализировать обнаружение естественно упорядоченных подмассивов (RUN).
+**Требования к визуализации:**
+  * Найти и выделить естественно упорядоченные последовательности (возрастающие/убывающие)
+  * Развернуть убывающие последовательности
+  * Отсортировать каждый RUN сортировкой вставками
+  * Слить RUN'ы с визуализацией слияния
+**Пример вывода:**
+  Анализ массива [5, 3, 2, 8, 9, 1, 4, 7]:
+  Поиск RUN'ов:
+    RUN 1 (убывающий): [5, 3, 2] → разворачиваем → [2, 3, 5]
+    RUN 2 (возрастающий): [8, 9]
+    RUN 3 (возрастающий): [1, 4, 7]
+  После сортировки RUN'ов вставками (минимальные улучшения):
+    RUN 1: [2, 3, 5]
+    RUN 2: [8, 9]
+    RUN 3: [1, 4, 7]
+  Слияние RUN 1 и RUN 2:
+    Сравниваем 2 и 8 → берем 2
+    Сравниваем 3 и 8 → берем 3
+    ...
+    Результат: [2, 3, 5, 8, 9]
+  Слияние с RUN 3:
+    Сравниваем 2 и 1 → берем 1
+    Сравниваем 2 и 4 → берем 2
+    ...
+    Итог: [1, 2, 3, 4, 5, 7, 8, 9]
+===== Критерии оценки =====
+  * **3 балла:** Реализован алгоритм сортировки, есть базовый вывод
+  * **4 балла:** Реализована визуализация согласно варианту, код структурирован
+  * **5 баллов:** Добавлена интерактивность (пошаговый режим/выбор скорости), понятный интерфейс, обработка ошибок
 **Вариант 1:** Массив: [64, 34, 25, 12, 22, 11, 90]
@@ Line 61: / Line 463: @@
 **Вариант 20:** Массив: [93, 81, 78, 65, 52, 39, 27, 14]
-**Вариант 2:** Вариант задачи 2 для лабораторной 3.1
-**Вариант 3:** Вариант задачи 3 для лабораторной 3.1
-**Вариант 4:** Вариант задачи 4 для лабораторной 3.1
-**Вариант 5:** Вариант задачи 5 для лабораторной 3.1
-**Вариант 6:** Вариант задачи 6 для лабораторной 3.1
-**Вариант 7:** Вариант задачи 7 для лабораторной 3.1
-**Вариант 8:** Вариант задачи 8 для лабораторной 3.1
-**Вариант 9:** Вариант задачи 9 для лабораторной 3.1
-**Вариант 10:** Вариант задачи 10 для лабораторной 3.1
-**Вариант 11:** Вариант задачи 11 для лабораторной 3.1
-**Вариант 12:** Вариант задачи 12 для лабораторной 3.1
-**Вариант 13:** Вариант задачи 13 для лабораторной 3.1
-**Вариант 14:** Вариант задачи 14 для лабораторной 3.1
-**Вариант 15:** Вариант задачи 15 для лабораторной 3.1
-**Вариант 16:** Вариант задачи 16 для лабораторной 3.1
-**Вариант 17:** Вариант задачи 17 для лабораторной 3.1
-**Вариант 18:** Вариант задачи 18 для лабораторной 3.1
-**Вариант 19:** Вариант задачи 19 для лабораторной 3.1
-**Вариант 20:** Вариант задачи 20 для лабораторной 3.1