Организация поиска элементов по заданному ключу

Практическое занятие № 4. «Поразрядная сортировка»

Цель работы

Ознакомиться и реализовать алгоритмы поразрядной LSD и MSD сортировок.

Поразрядная сортировка

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

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

- Строки - последовательности символов

- Двоичные числа – последовательности битов

- Десятичные числа – последовательности десятичных разрядов.

Каждый элемент такой последовательности имеет строго определенный размер. Сортировки, основанные на обработке за раз одного такого элемента называются поразрядными (radix).

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

Основа поразрядной сортировки – извлечь i- тый объект последовательности.

Существуют два базовых подхода: первый анализирует объекты слева направо (первыми обрабатываются наиболее значащие цифры). Такая сортировка называется MSD (most significant digit)- сортировкой.

Второй подход анализирует цифры справа налево (первыми обрабатываются меньшие разряды) – LSD (last significant digit).

Средства Си для реализации поразрядных сортировок

Для выделения i – того разряда десятичного числа x можно воспользоваться формулой . Например, извлечем разряд сотен числа 2875: (2875/100) mod 10 à28 mod 10 ==8

Для выделения символа строки используется обращение по индексу. Например, char *x – строка, x[i] – i -тый символ строки

При выделении i- того двоичного разряда можно использовать следующий алгоритм:

1. Выполнить сдвиг вправо на i.

2. Наложить на исходное число маску 1 (выполнить логическое умножение).

3. Полученное число вернуть в качестве результата.

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

// x - исходное число, d – номер разряда

int digit(int x, int d)

{ int k = x>>d;

k = k&1;

return k;}

MSD - сортировка

1.4.1. Поразрядная сортировка

Предположим, следующие латинские буквы имеют коды:

a 000	b 001	c 010	d 011
e 100	f 101	g 110	h 111

Дана последовательность e f d e c g h d е e, необходимо упорядочить ее. Просмотрим последовательность слева направо, и найдем первый ключ, который начинается с бита 1, далее просмотрим последовательность справа налево и найдем ключ, начинающийся с бита 0. Обменяем их местами и будем выполнять этот процесс пока индексы просмотров не пересекутся:

010 à

011

Первый шаг сортировки закончен. Получено два подмассива: с первой единицей и с первым нулем.

Рекурсивно применим ту же самую процедуру к полученным массивам по следующему разряду:

011	Без изменений, все элементы разряда равны 1.

По третьему разряду:

011

Сортировка первого подмасссива закончена, так как рассмотрен последний разряд

Начнем сортировать по второму разряду второй подмассив:

011

011 1 00

Сортировка по третьему разряду двух полученных подмассивов:

011 1 00

011 1 01

Сортировка закончена, получен отсортированный массив:

c d d e e e ef g h.

Алгоритм сортировки в общем виде можно записать следующим образом:

Radix_bin(X,F,L,d)

{

Если d<0 или F==L то выход

I=F, J = L;

1: пока I<J

если байт d в x[I] == 0 то I++

пока I<J

если байт d в x[j] == 1 то J++

Если I<J то меняем местами x[I] и x[J]

возврат на 1.

radix_bin(X,F,J,d-1)

radix_bin(X,I,L,d-1)

}

1.4.2. Поразрядная MSD сортировка

Если в быстрой двоичной сортировке разделение происходит на два подмассива (0 и 1), то MSD сортировка обобщает понятие поразрядной сортировки по произвольному основанию R – происходит разделение всего массива на R подмассивов.

Таким образом, в функции будет выполнено R рекурсивных вызовов.

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

3 4 2 7 9 à 3 7 9 16 25

Каждый элемент массива сложим с предыдущим. Далее просмотрим основной массив – если первая буква “a”, то ставим ее на 2 (3-1) место и первый элемент массива разделений уменьшаем: 2 7 9 16 25 и т.д..

Основная часть работы происходит на первом же этапе разделения. Можно улучшить алгоритм MSD если для сортировки подмассивов маленькой размерности использовать алгоритм простой сортировки.

1.4.3. Поразрядная LSD сортировка

Сортировка работает только в случае устойчивого способа перестановки элементов. К устойчивым сортировкам относится сортировка вставками, поэтому можно применить его. Рассмотрим на примере:

10000

0100 1

000 11

10 110

0 1001

Сортировка нерекурсивная.

На основании R выполняется аналогичным образом и остается такой же нерекурсивной.

Порядок выполнения

· Получите вариант задания у преподавателя.

· Составьте алгоритм поразрядной сортировки.

· Реализуйте алгоритм на языке Си.

· Проанализируйте полученные результаты.

Организация поиска элементов по заданному ключу

Цель работы

Ознакомиться с основными алгоритмами поиска элементов в массиве. Реализовать на языке Си различные методы поиска.

Прямой поиск

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

- найти количество заданных элементов;

- если заданных элементов несколько, то найти все элементы;

- если заданных элементов несколько, то найти первое вхождение заданного элемента и т.д..

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

Самый простой и неэффективный метод поиска – прямой поиск. Его алгоритм может быть описан следующим образом:

Поиск(массив X, элемент a)

{n – размер массива X;

ЦИКЛ()

ЕСЛИ (X[i]==a) вернуть i;

вернуть -1;

}

Функция возвращает -1, если поиск прошел неуспешно. В случае успеха функция возвращает индекс заданного элемента.

Очевидно, что время поиска прямо пропорционально размеру просматриваемого массива.

Для улучшения прямого поиска можно воспользоваться следующими стратегиями:

- пусть в системе высока вероятность того, что ранее найденный элемент будет и далее участвовать в поиске, тогда можно переносить найденный элемент в начало массива; тогда следующий поиск пройдет быстрее;

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

Бинарный поиск

Если данные массива упорядочены, то можно сократить время поиска, реализуя следующий алгоритм:

1. X – массив, n – размерность массива, a – значение для поиска.

2. F = 0, L = n-1

3. M = (F+L)/2 // найдем середину массива

4. ЕСЛИ (a==X[M]) ТО вернуть М // элемент найден

5. ЕСЛИ (a<X[M]) ТО L = M-1 // далее ищем в левой половине

6. ЕСЛИ (a]>X[M]) ТО F = M+1 // далее ищем в правой половине

7. ЕСЛИ (F<L) ТО вернуться на шаг 3.

8. Вернуть -1 // поиск прошел неуспешно.

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

Интерполяционный поиск

Этот поиск является улучшенной версией бинарного поиска для числовых отсортированных массивов. Предположим, что данные в массиве равномерно распределены на промежутке от 0 и до n. Очевидно, что чем больше значение, тем ближе оно находится к концу массива. Интерполяционный поиск позволяет определить размер массива, в котором будет производиться поиск в зависимости от значения искомого элемента. То есть, если ищется маленькое значение, то точка разделения будет находиться ближе к началу массива. При поиске больших значений точка разделения сдвинется к концу массива.

Алгоритм интерполяционного поиска выглядит следующим образом: