Введение в сортировку

Хеширование таблиц

Алгоритм поиска

low=0; high=n-l; search=-l; while(low<high)

{

mid=(int)(low+high)/2; if (key==k[mid])

{

search=mid;

break; }

if (key<k[mid])

high=mid-l; else

low=mid+l; }

Здесь key — аргумент поиска (число, которое записывается в ключевом поле искомой записи); search — переменная, которая хранит номер разыскиваемой записи; mid— номер записи, в которой осуществляется поиск необходимого значения ключевого поля; low и high — границы поиска; п — число ключей в массиве.

Хеширование — один из способов увеличения эффективности поиска [9]. Основная идея хеширования — подобрать некий способ преобразования значения ключа сразу в адрес записи. Таким образом, поиск становится вообще ненужным.

Поясним это на примере. Пусть в файле прямого доступа лежит структура со следующими полями (табл. 3.2): 1) номер накладной, 2) грузоотправитель, 3) грузополучатель, 4) груз, 5) количество единиц груза. Номер накладной обычно

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

Таблица 3.2 Поля структуры

Таблица 3.3 Дополнительная таблица индексов

Попробуем упростить процесс. Пусть мы имеем не более 1000 записей. Если бы значения ключа лежали в диапазоне 1 до 1000, то таблицу индексов можно построить иначе, а именно — заносить номер записи в ячейку таблицы, номер которой равен ключу (табл. 3.4). Ясно, что теперь для поиска записи с ключом, например, 282, достаточно было бы сразу обратиться к ячейке с номером 282 (прямой доступ), извлечь оттуда значение 23 и прочитать запись номер 23 в массиве (снова прямой доступ). Таким образом, поиск не нужен.

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

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

Таблица 3.4 Таблица

Вернемся к примеру.Если внимательно посмотреть на последнюю таблицу, то станет ясно, что в качестве хеш-функции мы взяли просто усечение номера накладной до последних трех цифр (это не худший метод хеширования). Однако, что делать, если имеется накладная с номером 207008282, а приходит документ с номером 010550282? Эта ситуация весьма типична и называется коллизией хеширования.

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

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве. Следовательно, методы сортировки важны особенно при обработке данных [1, 3, 9, 10, 13].

Зависимость выбора алгоритма от структуры данных — явление довольно частое, и в случае сортировки она настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов (внутренняя сортировка) и сортировка файлов (внешняя сортировка). Массивы обычно располагаются в оперативной памяти, для которой характерен быстрый произвольный доступ; файлы хранятся в более медленной, но более вместительной внешней памяти, на дисках.

Введем некоторую терминологию [3]. Пусть даны элементы ai,ci2, ...,a_n. Сортировка означает перестановку элементов в таком порядке а^\, ^аю., ■■■,^кп-, что при заданной упорядочивающей функции f(x) справедливо отношение

f(a_xl)<f(a_xl)<...<f(a_m).

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

struct item

{ int key;

описание других компонент;

}; ,

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

Сортировка массивов.Основное требование к методам сортировки массивов — экономное использование памяти. Это значит, что перестановки элементов нужно выполнять на том же месте оперативной памяти, где они находятся, и что методы, которые пересылают элементы из массива А в массив В, не представляют интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов, проводят в соответствии с их эффективностью, т.е. быстродействием. Удобная мера эффективности получается при подсчете числа необходимых сравнений ключей С и пересылок элементов М. Эти параметры зависят от числа сортируемых элементов п. Хорошие алгоритмы сортировки требуют порядка nlogn сравнений.

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

Методы сортировки массивов можно разбить на три класса [3]:

1) сортировка включениями;

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

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

Сравним эти методы. Используем массив а, описанный следующим образом:

int nambers[n\; .