Практическая работа №16

Визуализация алгоритмов сортировки

Цель работы: Изучить принципы работы основных алгоритмов сортировки (пузырьковая, вставками, быстрая), освоить методы визуализации данных и реализации пошаговой анимации с использованием библиотеки Qt на языке C++.

Основные теоретические положения

1. Пузырьковая сортировка (Bubble Sort)

Пузырьковая сортировка — это простейший алгоритм сортировки, который многократно проходит по списку, сравнивая соседние элементы и меняя их местами, если они расположены в неправильном порядке. Проходы по списку повторяются до тех пор, пока не останется ни одной пары элементов, требующих обмена, что означает, что список отсортирован [1].

Характеристика	Значение
Худшая сложность	O(n²)
Средняя сложность	O(n²)
Лучшая сложность	O(n)
Затраты памяти	O(1)
Стабильность	Да

2. Сортировка вставками (Insertion Sort)

Сортировка вставками — это алгоритм, который строит отсортированный массив по одному элементу за раз. Он работает путем итеративной вставки каждого элемента из несортированной части в его правильную позицию в уже отсортированной части [2].

Характеристика	Значение
Худшая сложность	O(n²)
Средняя сложность	O(n²)
Лучшая сложность	O(n)
Затраты памяти	O(1)
Стабильность	Да

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

Быстрая сортировка использует стратегию “разделяй и властвуй”. Она выбирает опорный элемент (pivot) и перераспределяет элементы массива так, чтобы элементы меньше опорного оказались слева, а больше — справа [3].

Характеристика	Значение
Худшая сложность	O(n²)
Средняя сложность	O(n log n)
Лучшая сложность	O(n log n)
Затраты памяти	O(log n)
Стабильность	Нет

4. Использование QTimer для анимации

Для создания пошаговой анимации в Qt-приложениях используется класс QTimer. Он позволяет запускать слот через определенные интервалы времени или однократно после заданного таймаута [4]. Это ключевой компонент для визуализации алгоритмов сортировки, так как каждый шаг алгоритма может быть выполнен при срабатывании таймера, что создает эффект анимации.

Основные методы QTimer:

• start(int msec): Запускает или перезапускает таймер. Сигнал timeout() будет излучаться каждые msec миллисекунд.
• stop(): Останавливает таймер.
• setInterval(int msec): Устанавливает интервал срабатывания таймера.
• setSingleShot(bool singleShot): Если true, таймер сработает только один раз.

Пример использования QTimer:

#include <QTimer>
#include <QObject>
#include <iostream>

class MyAnimator : public QObject {
    Q_OBJECT
public:
    MyAnimator(QObject *parent = nullptr) : QObject(parent) {
        QTimer *timer = new QTimer(this);
        connect(timer, &QTimer::timeout, this, &MyAnimator::onTimeout);
        timer->start(1000); // Срабатывает каждую секунду
    }

private slots:
    void onTimeout() {
        std::cout << "Таймер сработал!" << std::endl;
    }
};

5. Отрисовка графики с помощью QPainter

Класс QPainter используется для выполнения низкоуровневой отрисовки на виджетах и других устройствах рисования в Qt. Он позволяет рисовать примитивы (линии, прямоугольники, эллипсы), текст, изображения и сложные фигуры [5]. Для визуализации массива в виде столбцов QPainter является идеальным инструментом.

Отрисовка обычно происходит в переопределенном методе paintEvent(QPaintEvent *event) виджета. В этом методе создается объект QPainter, который затем используется для рисования.

Основные методы QPainter:

• begin(QPaintDevice *device): Начинает рисование на указанном устройстве.
• end(): Завершает рисование.
• setPen(const QPen &pen): Устанавливает перо (для контуров).
• setBrush(const QBrush &brush): Устанавливает кисть (для заливки).
• drawRect(const QRect &rectangle): Рисует прямоугольник.
• fillRect(const QRect &rectangle, const QBrush &brush): Заливает прямоугольник.

Пример использования QPainter:

#include <QWidget>
#include <QPainter>
#include <QPen>
#include <QBrush>

class MyWidget : public QWidget {
    Q_OBJECT
public:
    MyWidget(QWidget *parent = nullptr) : QWidget(parent) {}

protected:
    void paintEvent(QPaintEvent *event) override {
        Q_UNUSED(event);
        QPainter painter(this); // Рисуем на текущем виджете

        // Установка пера и кисти
        painter.setPen(QPen(Qt::black, 2)); // Черный контур толщиной 2 пикселя
        painter.setBrush(QBrush(Qt::blue)); // Синяя заливка

        // Рисование прямоугольника
        painter.drawRect(50, 50, 100, 150); // x, y, width, height

        // Рисование другого прямоугольника с другой заливкой
        painter.setBrush(QBrush(Qt::red));
        painter.drawRect(200, 50, 80, 120);
    }
};

Задания для выполнения

Для успешного выполнения практической работы необходимо реализовать приложение на C++ с использованием библиотеки Qt, которое будет визуализировать работу трех алгоритмов сортировки: пузырьковой, вставками и быстрой. Задание разделено на несколько ключевых этапов с подробными требованиями.

1. Проектирование и реализация пользовательского интерфейса (UI)

Цель: Создать интуитивно понятный и функциональный интерфейс для управления визуализацией.

Требования:

• Главное окно приложения: Должно быть создано как QWidget или QMainWindow.
• Область для рисования (CanvasWidget):
  • Выделите центральную часть окна под CanvasWidget — пользовательский виджет, унаследованный от QWidget.
  • Размер CanvasWidget должен быть достаточным для отображения 50-100 элементов массива (например, 800x600 пикселей).
  • На этом виджете будет происходить вся отрисовка элементов массива в виде гистограммы.
• Панель управления: Разместите элементы управления в отдельной области (например, справа или снизу от CanvasWidget) с использованием макетов (QVBoxLayout, QHBoxLayout).
  • Выбор алгоритма: QComboBox с тремя опциями:
    • “Пузырьковая сортировка”
    • “Сортировка вставками”
    • “Быстрая сортировка”
  • Кнопки управления:
    • QPushButton “Генерировать новый массив”: При нажатии генерируется новый случайный массив и сбрасывается состояние сортировки.
    • QPushButton “Старт”: Запускает пошаговую анимацию выбранного алгоритма.
    • QPushButton “Пауза”: Приостанавливает анимацию.
    • QPushButton “Шаг”: Выполняет один шаг алгоритма (активна только в режиме паузы).
    • QPushButton “Сброс”: Сбрасывает текущий массив в исходное (неотсортированное) состояние и останавливает анимацию.
  • Управление скоростью анимации: QSlider (с диапазоном, например, от 10 до 1000 мс) для регулировки интервала срабатывания QTimer.
• Отображение информации: QLabel для вывода текущего состояния (например, “Сортировка завершена”, “Пауза”, “Идет сортировка: Пузырьковая”).

2. Реализация генерации и отображения массива

Цель: Обеспечить динамическое создание и корректное графическое представление массива.

Требования:

• Генерация массива:
  • Реализуйте функцию, которая генерирует N случайных целых чисел в заданном диапазоне (например, от 1 до 100).
  • N должно быть настраиваемым (например, от 50 до 100 элементов по умолчанию).
  • Массив должен быть уникальным при каждой генерации (без повторяющихся значений, если это возможно, или с минимальной вероятностью повторений).
• Отображение гистограммы:
  • В CanvasWidget::paintEvent отрисуйте элементы массива в виде вертикальных столбцов.
  • Ширина каждого столбца должна быть фиксированной, а высота — пропорциональной значению элемента.
  • Между столбцами должен быть небольшой отступ для лучшей читаемости.
  • Масштабирование: убедитесь, что все столбцы помещаются в CanvasWidget и их высота адекватно отображает значения.

3. Реализация пошаговых алгоритмов сортировки

Цель: Интегрировать алгоритмы сортировки таким образом, чтобы каждый шаг мог быть визуализирован.

Требования:

• Пошаговая реализация: Каждый из трех алгоритмов (Пузырьковая, Вставками, Быстрая) должен быть реализован как набор функций, которые выполняют один логический шаг алгоритма за вызов.
  • Например, для пузырьковой сортировки один шаг может включать одно сравнение и, возможно, один обмен.
  • Для сортировки вставками — перемещение одного элемента на его правильную позицию.
  • Для быстрой сортировки — один шаг может быть частью процесса разбиения (partition) или переход к следующему подмассиву.
• Управление состоянием: В главном окне (или в отдельном классе-контроллере) необходимо хранить текущее состояние каждого алгоритма (например, индексы текущих элементов, границы отсортированных частей, стек для быстрой сортировки).
• Не рекурсивная быстрая сортировка: Для пошаговой визуализации быструю сортировку необходимо реализовать итеративно, используя явный стек для хранения диапазонов, которые нужно отсортировать. Это позволит контролировать каждый шаг без блокировки GUI.

4. Цветовая индикация состояния элементов

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

Требования:

• Цветовая схема: Определите и используйте следующую цветовую схему для столбцов:
  • Синий (или серый): Элементы в обычном состоянии.
  • Красный: Элементы, которые в данный момент сравниваются или обмениваются местами.
  • Желтый (или оранжевый): Опорный элемент (pivot) в быстрой сортировке.
  • Зеленый: Элементы, которые уже находятся на своих окончательных отсортированных позициях.
• Динамическое обновление: CanvasWidget должен получать информацию о текущих индексах, которые нужно подсветить, и перерисовывать себя с соответствующими цветами после каждого шага алгоритма.

5. Общие требования к реализации и оформлению

• Модульность: Разделите код на логические части (например, класс для главного окна, класс для области рисования, возможно, отдельный класс для логики сортировки).
• Комментарии: Код должен быть хорошо прокомментирован, особенно сложные участки и логика алгоритмов.
• Именование: Используйте осмысленные имена для переменных, функций и классов (например, currentElementIndex, compareElementIndex).
• Обработка граничных случаев: Убедитесь, что приложение корректно работает с пустыми массивами, массивами из одного элемента, уже отсортированными или обратно отсортированными массивами.
• Отзывчивость: Приложение должно оставаться отзывчивым во время анимации; никаких “зависаний” GUI.

Контрольные вопросы

1. Почему для визуализации алгоритмов в GUI-приложениях рекомендуется использовать таймеры, а не циклы?
2. В чем преимущество быстрой сортировки перед пузырьковой на больших объемах данных?
3. Как влияет выбор опорного элемента в Quick Sort на его производительность?
4. Что такое “стабильность” алгоритма сортировки и почему она важна?
5. Опишите, как реализовать пошаговое выполнение рекурсивного алгоритма (Quick Sort) без использования реальной рекурсии.

Рекомендуемая литература

1. Bubble Sort - GeeksforGeeks
2. Insertion Sort Algorithm - GeeksforGeeks
3. Quick Sort - GeeksforGeeks
4. QTimer Class | Qt Core | Qt 6.10.2
5. QPainter Class | Qt GUI | Qt 6.10.1
6. Шилдт Г. C++: Полное руководство. — М.: Диалектика, 2018.
7. Бланшет Ж., Саммерфилд М. Qt 4: Программирование GUI на C++. — М.: Кудиц-Пресс, 2008.