QThread — потоки / Визуализация процесса сортировки

В этой статье рассмотрен процесс создания многопоточных приложений на примере трех алгоритмов сортировки, которые работают в отдельных потоках: heapsort, buble sort и quicksort. Каждый  алгоритм будет визуализирован столбиковой диаграммой.

Начнем с конца! В результате мы получим вот такое приложение:

heap_buble_quick-sort

В Qt создание своего потока происходит в  3 этапа:

  1. Создаем класс наследующий (производный класс) QTheard
  2. Переопределеяем функцию run() — пишем в функции то, что должно происходить в потоке (в нашем случае в функции run() мы будем реализовывать алгоритмы сортировки)
  3. Запускаем поток QTheard::start();

Как визуализировать процесс сортировки

Рисовать будем на QGraphicsScene (далее — сцена). Так как у нас три алгоритма, для простоты создаем 3 различные сцены одинаковой высоты и ширины:

QGraphicsView предназначен для просмотра содержимого сцены.

И теперь самое главное, функция которая будет рисовать столбиковую диаграмму на QGraphicsScene:

Функция очень проста! Для тех кто не понял фразы «очищаем предыдущие «художества»» — удаляем с нашей сцены все что на ней есть, чтобы новые прямоугольники не рисовались поверх старых и не получалось творческое безобразие! И да, функция в качестве формальных параметров принимает номер сцены (напоминаю,  каждый алгоритм пляшет на своей сцене) и собственно сам массив с числами.

Создаем потоки

Теперь создадим первый поток,  и кстати, в этой статье — последний — не вижу смысла описывать здесь создание потока для каждого из алгоритмов. В этом потоке мы реализуем пирамидальную сортировку (heapsort). Сам алгоритм рассказывать не буду, в интернете достаточно информации.

Опишем интерфейс класса:

Теперь по порядку, сначала разберемся с наиболее сложным — формирование пирамиды:

Прокомментировать особо нечего. Информации конкретно по алгоритму можно найти много. Скажу только что usleep(100000) — предназначен чтобы замедлить визуализацию, без этого вы просто не увидите как перемещаются столбики. Конечно можно и убрать, если у вас компьютер настолько слаб, что будет лагать при выполнении этих операций 😉

Теперь функция run(), после выполнения которой мы получаем отсортированный массив:

«qRegisterMetaType(«QVector»);» —  без этой строчки у меня выдает следующую ошибку:

Ну и функция инициализации начальных параметров:

Вывод: все что нужно сделать в потоке запихиваем в функцию run() и запускаем поток методом start();

Теперь возвращаемся в класс MainWindow. Давайте реализуем функцию, которая будет генерировать массив из случайных чисел (при запуске программы и при нажатии на кнопку «Сгенерировать новый массив»):

Довольно забавная ситуация  c qrand() : каждый раз при запуске программы генерируются одни и те же числа. Чтобы добавить разнообразия в нашу жизнь, используется  qsrand (), которой передаем в качестве сида системное время:

Кому интересно, можете понаблюдать на разницу без и с qsrand().

Функция reset() на восстанавливает на всех графических сценах изначальный массив array (чтобы на всех сценах отображалась одинаковая картинка — столбиковая диаграмма при одинаковых начальных условиях):

При нажатии на кнопку start нам необходимо запустить все три потока и передать им соответствующие параметры (номер сцены и массив):

Напомню, что запуск потока происходит непосредственно в функции init().

На этом все. Привожу полный листинг *.cpp и *.h файлов (крайне не рекомендуется копировать код с блоков ниже, редактор может заменить некоторые символы на html-сущности):