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

Date: 2015-10-07; view: 419.

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

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

Рассмотрим алгоритм слияния (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 ;

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