====== Лабораторная работа 3.1: Алгоритмы сортировки с визуализацией ======

===== Общие требования =====
  * Язык программирования: любой (C++, Python, Java, C#)
  * Визуализация процесса сортировки обязательна
  * Программа должна показывать каждый шаг/проход алгоритма
  * Входные данные: массив из 10-15 элементов (целые числа)
  * Выходные данные: пошаговый вывод процесса сортировки + итоговый массив

===== Вариант 1: Пузырьковая сортировка (Bubble Sort) с пошаговым выводом =====

**Тип сортировки:** Внутренняя, обменная

**Задание:** Реализовать классическую сортировку пузырьком. На каждом проходе выводить текущее состояние массива и выделять сравниваемые элементы.

**Требования к визуализации:**
  * После каждого прохода выводить строку: "Проход X: [массив]"
  * Сравниваемые пары выделять скобками: (a b)
  * Обмены помечать символом "<->"

**Пример вывода:**
  Исходный массив: [5, 1, 4, 2, 8]
  
  Проход 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]

===== Вариант 2: Сортировка вставками (Insertion Sort) с гистограммой =====

**Тип сортировки:** Внутренняя, вставками

**Задание:** Реализовать сортировку вставками. Визуализировать процесс с помощью ASCII-гистограммы.

**Требования к визуализации:**
  * Каждый элемент отображается как столбец из символов '#'
  * Высота столбца пропорциональна значению элемента
  * Текущий вставляемый элемент выделять цветом/символом '*'
  * Отсортированную часть отделять вертикальной чертой '|'

**Пример вывода:**
  Шаг 1: Вставляем 4
  [###] | [#] [#####] [##]
    3     1     5     2
  
  Шаг 2: Вставляем 5
  [#] [###] | [#####] [##]
   1    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]
  
  Визуализация счетчиков:
    2: ##
    3: ##
    1: #
    4: #
    8: #
  
  Восстановление:
    Берем 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 (единицы):
    Распределение по корзинам:
    0: [170, 90]
    2: [2, 802]
    4: [24]
    5: [45, 75]
    6: [66]
    Сборка: [170, 90, 2, 802, 24, 45, 75, 66]
  
  Разряд 2 (десятки):
    Распределение по корзинам:
    0: [2, 802]
    2: [24]
    4: [45]
    6: [66]
    7: [170, 75]
    9: [90]
    Сборка: [2, 802, 24, 45, 66, 170, 75, 90]

===== Вариант 10: Пирамидальная сортировка (Heap Sort) с визуализацией кучи =====

**Тип сортировки:** Внутренняя, пирамидальная

**Задание:** Реализовать пирамидальную сортировку. Визуализировать построение max-кучи и процесс извлечения элементов.

**Требования к визуализации:**
  * Показывать бинарное дерево в текстовом виде
  * Выделять текущую "просеиваемую" вершину
  * Показывать обмен корня с последним элементом

**Пример вывода:**
  Построение кучи:
        5
       / \
      1   4
     / \
    2   8
  
  Просеиваем 5:
        8
       / \
      5   4
     / \
    2   1
  
  Сортировка:
    Корень=8, меняем с последним=1
        1
       / \
      5   4
     /
    2
    Просеиваем 1:
        5
       / \
      1   4
     /
    2
    ...

===== Вариант 11: Сортировка бинарным деревом (Binary Tree Sort) с графическим выводом =====

**Тип сортировки:** Внешняя (структура данных - дерево)

**Задание:** Реализовать сортировку с помощью бинарного дерева поиска. Визуализировать построение дерева.

**Требования к визуализации:**
  * Показывать вставку каждого элемента в дерево
  * Отображать дерево с отступами (правые поддеревья с большим отступом)
  * Показать симметричный обход (in-order traversal) для получения отсортированного массива

**Пример вывода:**
  Вставляем 5:
    5
  
  Вставляем 3:
    5
   /
  3
  
  Вставляем 7:
    5
   / \
  3   7
  
  Вставляем 2:
      5
     / \
    3   7
   /
  2
  
  Обход (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]

**Вариант 2:** Массив: [5, 1, 4, 2, 8]

**Вариант 3:** Массив: [100, 90, 80, 70, 60, 50, 40, 30, 20, 10]

**Вариант 4:** Массив: [3, 6, 1, 8, 4, 9, 2, 7, 5]

**Вариант 5:** Массив: [45, 23, 67, 12, 89, 34, 56, 78]

**Вариант 6:** Массив: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

**Вариант 7:** Массив: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

**Вариант 8:** Массив: [29, 10, 14, 37, 13, 25, 48, 7]

**Вариант 9:** Массив: [55, 33, 77, 11, 99, 44, 66, 22, 88]

**Вариант 10:** Массив: [15, 25, 35, 45, 55, 65, 75, 85, 95]

**Вариант 11:** Массив: [95, 85, 75, 65, 55, 45, 35, 25, 15]

**Вариант 12:** Массив: [42, 17, 89, 63, 31, 76, 24, 58]

**Вариант 13:** Массив: [8, 3, 1, 6, 9, 2, 7, 4, 5]

**Вариант 14:** Массив: [100, 50, 25, 75, 12, 37, 62, 87]

**Вариант 15:** Массив: [19, 28, 37, 46, 55, 64, 73, 82, 91]

**Вариант 16:** Массив: [91, 82, 73, 64, 55, 46, 37, 28, 19]

**Вариант 17:** Массив: [6, 2, 9, 4, 7, 1, 8, 3, 5]

**Вариант 18:** Массив: [33, 66, 99, 11, 44, 77, 22, 55, 88]

**Вариант 19:** Массив: [14, 27, 39, 52, 65, 78, 81, 93]

**Вариант 20:** Массив: [93, 81, 78, 65, 52, 39, 27, 14]