NewBlock sort – фундаментальный алгоритм сортировки со сложностью O(n*log(n/2))

Welcome! Run-Time Systems

NewBlock sort - фундаментальный алгоритм сортировки со сложностью O(n*log(n/2))

Сортировка – один из фундаментальных алгоритмов программного обеспечения. Много изобретено в данном

направлении, но оптимальных решений так и не найдено, сложность решений и скорость обработки данных оставляют желать лучшего. Все алгоритмы многократно описаны и опубликованы в специальных изданиях и в Internet.

Кратко информация для сравнения по часто применяемым алгоритмам сортировки данных приведена в Таблице 1.

В данной статье рассматривается совершенно другой алгоритм, более простой и эффективный – блочный

(NewBlock 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 записей (чисел ).

Для более полного понимания алгоритма NewBlock sort

на Рис.1, Рис.2 и Рис.3 показана сортировка массива

из 16 чисел.

--- Черным цветом показаны операции сравнения.

--- Красным цветом показаны операции переноса

после сравнения.

--- Синим цветом показаны операции переноса

без сравнения.

При нечетном проходе данные из массива 1 переносятся в массив 2, при четном из массива 2 в массив 1.

Теперь об использовании памяти:

Если сортируются массивы чисел, то дополнительной памяти потребуется в размере n –

первоначальный размер массива.

Если сортируются записи, то дополнительной памяти потребуется 2n под указатели.

NewBlock sort алгоритм просто прекрасен для работы во многопотоковом исполнении на многоядерных

процессорах, позволяя запускать следующий проход сортировки не ожидая завершения предыдущего прохода,

что в разы уменьшает время сортировки.

Большие массивы записей (чисел) можно сортировать, разделив их на меньшие части на компъютерах в сети,

что еще больше сокращает время сортировки.

NewBlock sort алгоритм практически реализован на языке C в СУРБД Start-RTS+, кроссплатформенной системе

управления реляционными базами данных, предназначенной для использования в приложениях, работающих

без каких-либо изменений кода в среде операционных 64разрядных систем MX-Linux и Windows.

На базе Start-RTS+ разработана прикладная технологическая система Смета-RTS для расчета смет в области

строительства с нормативными базами регионов России.

e-mail:rts@rtsrts.com