Распределяющая сортировка от младшего разряда к старшему

Вышеописанным методом можно выполнять сортировку чисел лишь из небольшого диапазона (так как массив c должен иметь приемлемую длину). Алгоритм распределяющей сортировки берёт за основу алгоритм сортировки подсчётом и позволяет выполнять сортировку чисел (и некоторых других типов) произвольной разрядности. Сначала выполняется сортировка по младшему разряду (в качестве разрядов обычно выступают байты или двухбайтные слова), затем – по следующему и т.д. до старшего. При этом используется тот факт, что сортировка подсчётом является устойчивой, в результате чего данные будут корректно отсортированы (см. начало главы).

Рассмотрим реализацию алгоритма. Сортировка подсчётом немного усложняется – добавляется код для выделения значения заданного разряда-байта, при этом используются битовые операции сдвига влево <<, сдвига вправо >> и побитового “И” &.

 

//сортировка подсчетом по байту с номером bytenum

void countsort(unsigned int a[], int n, int bytenum)

{ int c[256]; int i;

int shift = bytenum * 8; //смещение этого байта в битах

int mask = 0xFF << shift; //битовая маска для выделения разряда

//подсчитываем количества

memset(c,0,sizeof(c));

for (i=0; i<n; i++) c[ (a[i]&mask) >> shift ]++;

//подсчитываем сумму с накоплением

for (i=1; i<256; i++) c[i]+=c[i-1];

//заполняем результирующий массив b

unsigned int *b = new unsigned int[n];

memset(b,0,sizeof(int)*n);

for (i=n-1; i>=0; i--)

{ b[--c[(a[i]&mask)>>shift]]=a[i];

}

memcpy(a,b,n*sizeof(int));

delete[] b;

}

//Собственно сортировка будет заключаться в вызове

// данной функции для всех разрядов:

void radsort(int a[], int n)

{ for(int i=0; i<sizeof(int); i++)

countsort(a, n, i);

}

Если k – число разрядов в сортируемых числах, то сложность алгоритма составляет Θ(kn). Обычно k ограничено константой, и в этом случае время работы составляет Θ(n). Таким образом, данный алгоритм является наиболее быстрым из вышерассмотренных (хотя разница становится заметной лишь при больших объёмах данных).

Недостатком алгоритма является зависимость от типа сортируемых данных: необходимо, чтобы данные допускали возможность разбития на разряды и их количество было ограничено. Примерами таких типов данных являются числа и короткие строки.

Ещё один недостаток алгоритма – использование вспомогательного массива такого же размера, как и исходный.

Распределяющая сортировка от старшего разряда к младшему

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

void ssort(char* a[], int n, int k)

{ static char **b = new char* [n];

static int c[256]; int i,j;

//подсчет количеств каждого значения i-го символа

memset(c,0,sizeof(c));

for(i=0; i<n; i++) c[(unsigned char)a[i][k]]++;

//сумма с накоплением

for(i=1; i<256; i++) c[i]+=c[i-1];

//сортировка по i-му разряду

for(i=n-1; i>=0; i--)

b[--c[(unsigned char)a[i][k]]] = a[i];

memcpy(a,b,sizeof(char*)*n);

//для каждой группы с одинаковым значением i-го разряда

//рекурсивно выполняем сортировку по (i+1)-му разряду

i=0;

while((i<n) && (a[i][k]==0)) i++;

while(i<n)

{ j = i;

while((j<n) && (a[i][k]==a[j][k])) j++;

if (j>i+1) ssort(a+i, j-i, k+1);

i=j;

}

}

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

Однако, в среднем время выполнения значительно меньше, так как сортировка группы завершается, как только она начинает состоять из одной строки. Если считать, что длина префикса, которой каждая строка уникально отличается от другой, ограничена некоторой небольшой константой (что недалеко от истины), то время работы составит O(n), где n – число строк.

Структуры и алгоритмы для поиска данных

Общие сведения

Постановка задачи поиска

Слово «поиск» имеет очень широкое толкование, поэтому, прежде чем переходить к материалу данной главы, поясним суть задачи.

Пусть имеется совокупность данных, состоящая из отдельных элементов, каждый из которых представляет собой запись из нескольких полей. Одно из полей выделим в качестве ключа для поиска, остальные поля образуют связанную с ключом информацию (точно так же, как в задаче сортировки — key и satellite data). При этом в одной записи вместе с ключом может храниться либо реальная информация, либо ссылка на другую запись, где хранится информация. Последняя ситуация является стандартной в базах данных, где поиск обычно ведется по нескольким различным ключам и по каждому из них создается своя структура для поиска (а реальная информация хранится в другом месте).

Задача поиска формулируется так — найти запись (или несколько записей), значение ключа которых совпадает с искомым значением. При этом становится доступной связанная с ключом информация. Обычно получение этой информации и является целью поиска. Иногда поиск может преследовать и более скромную цель — определить наличие или отсутствие записи с искомым значением ключа в совокупности данных. Например, если имеются данные о книгах в библиотеке, то, используя шифр книги в качестве ключа для поиска, можно получить как полную информацию о книге (автор, название, год издания и т.д.), так и просто выяснить, есть ли такая книга в наличии.

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

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

· найти первую попавшуюся запись;

· найти все записи.

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

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

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

· Будем считать, что выбор структуры данных в оперативной памяти производится исключительно из соображений эффективного поиска, при этом допустимы некоторые дополнительные расходы памяти, которые окупятся ускорением поиска.

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

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

Можно сформулировать этот вывод и так — задача поиска сводится к реализации абстрактного типа данных, который поддерживает эти три базовых операции. В литературе встречаются различные названия такого АТД, например, таблица [7, 13] или словарь [3]. Название и формальная функциональная спецификация в данном случае не имеют принципиального значения, поскольку постановка задачи понятна, а формальные соглашения по реализации будут приведены ниже.