Стр. 94 - Основы алгоритмов и структур данных

92 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Для хранения текущей “последовательности” применяется очередь Q*.
Также используется массив Q, состоящий из m очередей, в котором очередь
Q[i] предназначена для хранения тех элементов, у которых число i стоит в
компоненте рассматриваемой в данный момент.
procedure Sort
{
<поместить x 1, x2, …, xn в Q*>
for (j=1; j<=p; j++)
{
//очистка очередей
for(k=0;k<m-1;k++)
{
Q[j]=λ;
}
while (Q* не пусто)
{
Пусть xi первый элемент в очереди Q*,
тогда перемещаем xi в очередь Q[xij]
}
for(k=0;k<m-1;k++)
{
Присоединяем Q[k] к концу очереди Q*
}
}
}
Анализ быстродействия
Анализ этого алгоритма должен отличаться от анализа других алгоритмов
сортировки, поскольку мы не можем подсчитывать число сравнений имен и
перестановок. Вместо этого, мы будем подсчитывать общее число операций
очереди. Всегда имеется р проходов по таблице, и каждый проход требует
исключения из Q* каждого имени и включения его в одну из очередей Q[i].
Отсюда следует, что всего в очередях имеется 2np операций
включения/исключения. Каждый проход требует также (m – 1) сцеплений для
получения Q* из Q0 .....Qm -1, и поэтому имеется всего (m – 1)*р операций
сцепления очередей.
Чтобы поместить элемент xi в некоторую очередь, в действительности надо
сдвинуть лишь указатель на xi. Таким образом, операция сцепления или
включения/исключения может быть выполнена за постоянное время.
Поэтому алгоритм требует времени O((n+m)p).