Юрий Вагин, инженер-физик. Специальность — автоматика и электроника.
В статье рассматривается новый Blocksort— фундаментальный алгоритм сортировки со сложностью O(n*log(n/2)), прекрасный для работы во многопотоковом исполнении на многоядерных процессорах, поскольку позволяет запускать следующий проход сортировки, не ожидая завершения предыдущего прохода, что в разы уменьшает время сортировки.
Сортировка — один из фундаментальных алгоритмов программного обеспечения. Много изобретено в данном направлении, но оптимальных решений так и не найдено, сложность решений и скорость обработки данных оставляют желать лучшего. Все алгоритмы многократно описаны и опубликованы в специальных изданиях и в Internet. Краткая информация для сравнения по часто применяемым алгоритмам сортировки данных приведена в табл. 1.
В данной статье рассматривается совершенно другой алгоритм, более простой и эффективный, — блочный (Block sort), с двумя уровнями сложности: лучшей (min) — O((n/2)*log(n)) и худшей (max) — O(n*log(n/2)),
соотношением max/min = 2*(1-1/log(n)) и всегда известным количеством проходов при сортировке = log(n).
Весь массив записей (чисел) представляется в виде блоков и полублоков:
- на первом проходе размер блока равен 2, полублока — 1;
- на втором проходе размер блока равен 4, полублока — 2;
- на третьем проходе размер блока равен 8, полублока — 4;
- на четвертом проходе размер блока равен 16, полублока — 8;
- и так далее, то есть размер блока всегда равен 2 в степени номера прохода.
Для примера при количестве записей 64 необходимо выполнить log(64) = 6 проходов и сравнить: в лучшем случае (n/2)*log(n) = (64/2)*log(64) = 192 записи (числа), в худшем случае n*log(n/2) = 64*log(64/2) = 320 записей (чисел).
Для более полного понимания алгоритма Block sort на рис.1-3 показана сортировка массива из 16 чисел:
--- черным цветом показаны операции сравнения;
--- красным цветом показаны операции переноса после сравнения;
--- синим цветом показаны операции переноса без сравнения.
При нечетном проходе данные из массива 1 переносятся в массив 2, при четном — из массива 2 в массив 1.
Теперь об использовании памяти:
- если сортируются массивы чисел, то дополнительной памяти потребуется в размере n — первоначальный размер массива;
- если сортируются записи, то дополнительной памяти потребуется 2n — под указатели.
Алгоритм Block sort просто прекрасен для работы во многопотоковом исполнении на многоядерных процессорах, поскольку позволяет запускать следующий проход сортировки, не ожидая завершения предыдущего прохода, что в разы сокращает время сортировки.
Большие массивы записей (чисел) можно сортировать, разделив их на меньшие части на компьютерах в сети, что еще больше сокращает время сортировки.
Алгоритм Block sort практически реализован на языке C в СУРБД Start-RTS+ — кроссплатформенной системе управления реляционными базами данных, предназначенной для использования в приложениях, которые работают без каких-либо изменений кода в среде операционных 64-разрядных систем MX-Linux и Windows.
На базе Start-RTS+ разработана прикладная технологическая система Смета-RTS для расчета смет в области строительства с нормативными базами регионов России.
