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

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

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

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

Требования к визуализации:

• После каждого прохода выводить строку: “Проход 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]

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

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

Требования к визуализации:

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

Пример вывода:

Шаг 1: Вставляем 4
[###] | [#] [#####] [##]
  3     1     5     2

Шаг 2: Вставляем 5
[#] [###] | [#####] [##]
 1    3       5     2

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

Задание: Реализовать сортировку выбором. Создать эффект анимации в консоли (очистка экрана и перерисовка).

Требования к визуализации:

• Использовать модули времени (sleep) и очистки экрана (clear/cls)
• Показывать поиск минимального элемента
• Найденный минимум и текущую позицию для обмена выделять разными цветами
• Выводить счетчик сравнений

Пример вывода (кадры анимации):

[5] {1} [4] [2] [8]  (Поиск минимума: {1} - кандидат)
[5] [1] [4] {2} [8]  (Найден новый минимум {2})
Обмен: [1] <-> [5]
[1] [5] [4] [2] [8]  (После обмена)

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

Задание: Реализовать быструю сортировку (алгоритм Хоара). Визуализировать процесс в виде дерева рекурсии.

Требования к визуализации:

• Показывать выбор опорного элемента (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, 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]

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

Задание: Реализовать двунаправленную пузырьковую сортировку. Визуализировать направление движения.

Требования к визуализации:

• Использовать стрелки для показа направления прохода (→ и ←)
• После каждого прохода показывать границы отсортированной части
• Выводить текущее положение “шейкера”

Пример вывода:

Исходный: [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]

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

Задание: Реализовать сортировку Шелла. Показать влияние выбора шага (последовательность Шелла: 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]

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

Задание: Реализовать сортировку подсчетом для чисел в небольшом диапазоне (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]

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

Задание: Реализовать поразрядную сортировку (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]

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

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

Требования к визуализации:

• Показывать бинарное дерево в текстовом виде
• Выделять текущую “просеиваемую” вершину
• Показывать обмен корня с последним элементом

Пример вывода:

Построение кучи:
      5
     / \
    1   4
   / \
  2   8

Просеиваем 5:
      8
     / \
    5   4
   / \
  2   1

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

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

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

Требования к визуализации:

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

Пример вывода:

Вставляем 5:
  5

Вставляем 3:
  5
 /
3

Вставляем 7:
  5
 / \
3   7

Вставляем 2:
    5
   / \
  3   7
 /
2

Обход (in-order): 2, 3, 5, 7

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

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

Требования к визуализации:

• Позицию гнома отмечать символом '@'
• Показывать движение вперед (→) и назад (←)
• Выводить каждое перемещение гнома

Пример вывода:

[@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 - норм, вперед до конца)

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

Задание: Реализовать сортировку расческой (улучшенный пузырек с уменьшающимся шагом). Визуализировать влияние фактора уменьшения.

Требования к визуализации:

• Показывать текущий шаг (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, без обмена
  ...

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

Задание: Реализовать сортировку чет-нечет (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]

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

Задание: Реализовать упрощенный 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]