УП_САОД_2003

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

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

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

Применение большинства алгоритмов внутренней сортировки для сортировки файлов требует порядка O(n) проходов. Однако, если несколько модифицировать алгоритм сортировки слиянием (см. п. 3.5.2.8), то можно произвести сортировку, осуществляя порядка O(log n) проходов.

Основное отличие сортировки слиянием для файлов, заключается в следующем. Вся сортируемая последовательность данных разбивается на два файла f₁ и f₂. Желательно, чтобы количество записей в этих файлах было поровну. Как и в алгоритме внутренней сортировки, считаем, что любой файл состоит из участков длиной 1. Затем можно объединить участки длины 1 и распределить их по файлам g₁ и g₂ в виде участков длины 2. После этого делаем f₁ и f₂ пустыми и объединяем g₁ и g₂ в f₁ и f₂, которые затем можно организовать в виде участков длины 4 и т.д.

После выполнения i подобного рода проходов, получатся два файла, состоящие из участков длины 2ⁱ. Если 2ⁱ  n, тогда один из этих двух файлов будет пустым, а другой будет содержать единственный участок длиной n, то есть будет отсортирован. Так как 2ⁱ  n при i  log n, то нетрудно заметить, что в этом случае будет достаточно порядка O(log n) проходов по данным.

Пример внешней сортировки слиянием приведен на рисунке ниже.

Рисунок 49. Внешняя сортировка слиянием

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

Содержание