Сд типа хеш-таблица.

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

Операция включения элемента в таблицу.

Перед включением элемента в таблицу определяют его адрес с помощью хеш-функции: A = h(K), где K – ключ, а А – адрес элемента таблицы, причем 0  А  N-1, т.е. хеш-функция – отображение множества ключей на множество адресов.

A = K mod N = (C₁  k + C₂) mod N, где N – количество адресов в таблице.

“Хорошая” хеш-функция – это функция, которая быстро вычисляется и минимизирует количество коллизий. Коллизия – это ситуация, когда для разных ключей адрес один и тот же, т.е. h(k_i) = h(k_j), где i  j. Минимизации можно добиться, если равномерно распределить элементы по адресному полю таблицы.

После вычисления адреса элемента таблицы есть две возможности размещения элемента:

1. поместить этот элемент по адресу, если адрес свободен;

2. если вычисленный адрес занят, то повторить хеширование, т.е. совершить рехеширование по следующей формуле: A1 = (A+C) mod N.

Таким образом, алгоритм включения элемента в таблицу будет иметь следующий вид:

1. Вычисление ключа с помощью хеш-функции. Если вычисленный адрес таблицы свободен, то помещаем в него элемент. Конец алгоритма.

2. Если вычисленный адрес таблицы занят, то перевычисляем адрес (проводим рехеширование) и переходим к п.1.

Чтобы процесс размещения элементов был равномерным, адресное поле таблицы делается больше множества ключей на 10-15%.

Операция исключения элемента из таблицы:

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

2. Если по вычисленному адресу располагается искомый ключ, то запись найдена и ее удаляют. Конец алгоритма.

3. Если вычисленный адрес пуст, то элемента с заданным ключом в таблице нет. Конец алгоритма.

4. Если элемент таблицы содержит другой ключ, то перевычисляем (рехешируем) адрес и переходим к п.2.

Сортировки. Улучшенные методы сортировок.

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

Формулировка задачи может быть записана следующим образом.

Если даны элементы а₁, а₂ ,…, а_n, то сортировка означает перестановку этих элементов в массив а_к1, а_к2,…,а_кn где при заданной функции упорядочения f справедливы отношения f(а_к1)f(а_к2) …f(а_кn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является ключом элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке; неустойчивым – в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

1. сортировка вставками;

2. сортировка выбором;

3. сортировка обменом.

Все сортировки представляют собой поиск со вложенными циклами. Сложность сортировок обменом и выбором: O(N²). Особенность же сортировки включением в том, что данная сортировка зависит от степени упорядочивания исходной таблицы.

Рассмотрим улучшенные методы сортировок:

1) Сортировка Шелла. – это улучшенный метод сортировки включениями. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере.

Пример:

Первичный массив ключей	X1 25	X2 57	X3 82	X4 63	X5 90	X6 75	X7 80
Просмотр 1 Шаг 5 Проходов 5	25	57	82	63	90	75	80
Просмотр 2 Шаг 3 Проходов 3	25	57	82	63	90	75	80
Просмотр 3 Шаг 1 Проходов 1	25	57	75	63	90	82	80
Отсортированный массив ключей	25	57	63	75	80	82	90

При первом просмотре группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х₁,Х₆), (Х_2,Х₇), (Х₃), (Х₄), (Х₅); при втором проходе — элементы, отстоящие друг от друга на три позиции: (Х₁,Х_4,Х₇), (Х_2,Х₅), (Х_3,Х₆); при третьем — на 1 позицию.

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходным. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро – О(N²) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становиться ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то О(N) < порядок ФBC < О(N²).

Если некоторый массив частично отсортирован с использованием шага k, а затем сортируется частично с использованием шага j, то данный массив остается частично отсортированным по шагу k, т.е. последующие частичные сортировки не нарушают результата предыдущих сортировок.

В случае правильного выбора шагов порядок ФВС будет выглядеть как О(N^1.2). Д. Кнут предложил выбирать шаги из следующего ряда: 1, 4, 13, 40, 121, … , а вычислять их по следующей формуле: h_k–1 = 3 h_k +1; h_t = 1; t = [log ₃ N] – 1 (количество просмотров), где N – размерность исходного массива. Т.е. элементы должны быть взаимно простыми числами. Исходя из этого порядок сортировки может быть аппроксимирован величиной О(N(log ₂ N)).

2) Быстрая сортировка выбором. Улучшить сортировку выбором можно, если после каждого прохода получать больше информации, чем просто идентификация минимального элемента.

Пример:

k1 30	k2 10	k3 40	k4 20	k5 15	k6 17	k7 45	k8 60
10		20		15		45
10				15
10

10 – элемент MaxInt.

k1(N-1) – количество просмотров; log ₂ N – высота бинарного дерева.

Мы проходим от корня к листу по тому пути, по которому шел минимальный элемент (шаг 2). Затем осуществляем модификацию бинарного дерева. Общее количество модификаций: k2log ₂ N  (N-1).

Алгоритм быстрой сортировки выбором:

1. Сравниваем пары соседних ключей и запоминаем значение меньшего ключа из каждой пары.

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

3. Вносим значение корня, найденное в п.2, в массив упорядоченных ключей.

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

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

6. Повторяем пп.3-6, пока минимальным элементом не будет MaxInt.

Анализ быстрой сортировки выбором.

k1(N-1)+ k2log ₂ N(N-1) = О(N  log ₂ N) (ФВС = порядок)

2) Быстрая обменная сортировка (сортировка Хоара) – лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар окрестил его быстрой сортировкой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Алгоритм быстрой обменной сортировки:

1. Выбираем первый ключ в таблице в качестве разделителя.

2. Располагаем ключи меньшие разделителя до него, а большие – после.

3. Если число ключей до разделителя больше 1, то применяем алгоритм в целом.

4. Если число ключей после разделителя больше 1, то применяем алгоритм в целом. Конец алгоритма.

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

П.2 выполняется следующим образом: просматриваем массив от краев к центру и меняем местами ключи, нарушающие порядок.

30	10	40	20	15	17	45	60
30	( 10	17	20	15	40	45	60 )
……………………………………………………………………….
( 10	17	20	15 )	30	( 40	45	60 )
……………………………………………………………………….

Анализ сортировки Хоара.

• Количество элементов N = 2^m , m = log ₂ N, где N – количество элементов.

• Будем считать, что разделитель попадает в середину массива.

Подсчитаем количество сравнений:

Если воспользоваться алгоритмом на упорядоченную таблицу, то порядок будет O(N²).

Для определения разделителя имеются разные алгоритмы.