Автор: Александр ДЕНИСЕНКО aden@online.ru, aledin@academy.ru

Сортировка Шелла является асимптотически оптимальной по сложности в смысле числа попарных сравнений элементов множества, предназначенного для сортировки. Если множество состоит из N элементов, то сложность такой сортировки - примерно N*LogN (логарифм двоичный).

В больших базах и хранилищах данных значительное время могут занимать сортировки множеств специфической природы - натуральных чисел ограниченного диапазона (это порядковая нумерация типа Identity и аналогичные ей). Особенно актуально это в многозвенной клиент-серверной модели, когда основные массовые алгоритмы удобно делать на сервере, а на клиентской или промежуточной машине - переходить от натуральных кодов объектов к их изображению на экране в виде текстовых строк. В этом случае интерес может представлять специальная сортировка, асимптотически более эффективная (на натуральных числах).

Итак, имеется множество М={i1,…,ik} причем все i1,…,ik<N.
Требуется получить множество S, состоящее из элементов M в порядке возрастания (убывания).
Алгоритм состоит из не более чем трех шагов.
Шаг 1(подготовительный). Выделяем в памяти массив A[i] из N битов и обнуляем его.
Шаг 2 (основной). Считываем поочередно элементы массива M (одномерный проход) и для каждого элемента i устанавливаем в единицу бит A[i].
Шаг 3 (дополнительный). Проходим по массиву A[i] и для каждого единичного бита выдаем на выход - во множество S - номер соответствующего бита.

Нетрудно видеть, что алгоритм линеен, то есть его сложность - C*K.
Шаг 1 назван подготовительным, так как соответствующий массив может храниться в системе изначально (скажем, современная операционная система при выделении памяти сама заполняет его нулями по требованиям стандарта безопасности). Можно и заготовить такую константу.
Для множеств мощности до 1 миллиона - это всего 128 килобайт - две страницы сервера баз данных. Для множеств мощности до 100 миллионов потребуется обнуляемый вектор размера 12 мегабайт. Шаг 3 может и не требоваться - если результат носит промежуточный характер - мы просто перешли к другой кодировке множества.

Что касается теоретико-множественных операций над множествами рассматриваемой природы, то они сводятся очевидным образом к сортировке. В самом деле, для двух множеств M1 и M2 следует завести по вектору из нулей, затем выполнить Шаг 2 сортировки. Далее остается провести необходимую булевскую операцию (дизъюнкцию для объединения множеств, конъюнкцию - для пересечения и т.д.) и результат готов. Уместно заметить, что во многих системах разность множеств строится существенно сложнее суммы - что неестественно (сумма и разность чисел в процесссоре идет одинаково быстро, так как никакой разницы в алгоритмах нет).

Кажущийся парадокс нарушения известного теоретического результата связан со спецификой данных и сменой функционального базиса. Сортировка Шелла оптимальна при базисе, состоящем из операций попарного сравнения двух элементов. Мы просто выбрали другой функциональный базис.

С физической точки зрения парадокса и нет - так как поиск нужного бита в массиве требуе двоичного логарифма прохода по массиву. Но это операция, погруженная в элментную базу машины и потому представляющаяся атомарной.

[В начало]