Внешняя сортировка

СД типа хеш-файл.

Осуществляется отображение n:1. Хеширование является реализацией вышерассмотренной идеи. Хеширование задается функцией:

Function h (key.Tk): 0..N;

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

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

A = k mod N – функция хеширования (N – простое число)

[k mod (10000/100)]

h(k) = B + m[k mod (10 ⁿ/10 ^l)], где B и m – константы, n > l.

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

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

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

Рассмотрим алгоритм слияния (x, y, z – ключи в файлах):

Имеем: x₁ £ x₂ £ … £ x_n (1 файл); y₁ £ y₂ £ … £ y_m (2 файл); z₁ £ z₂ £ … £ z_n+m (3 файл).

1. i=1, j=1, k=1;

2. найти наименьшее;

если x _i < y _j, то идти к п.3 иначе к п.5;

3. вывести x _i; z _k ¬ x _i; i=i+1; k=k+1;

если i £ n, то идти к п.2;

4. вывести y _j … y _m , т.е. z _k … z _n+m ¬ y _j … y _m;

конец алгоритма.

5. вывести y _j; z _k ¬ y _j; k=k+1; j=j+1;

если j £ m, то идти к п.2;

6. вывести x _i … x _n , т.е. z _k … z _n+m ¬ x _i … x _n;

конец алгоритма.

Дата добавления: 2014-01-07