|
||||||||||||||||||||||||||||||||||||||||||||||||||||
Алгоритмы сортировки.Многофазная сортировка.Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну.Пример для 3-х серий, слияемых на 4-ю: 3 7 9 3 7 9 3 7 9 7 9 7 9 { 2 4 6 1 { 2 4 6 1 2 { 4 6 1 2 3 { 4 6 1 2 3 4 { 6 1 5 8 5 8 5 8 5 8 5 8 7 9 7 9 9 1 2 3 4 5 { 6 1 2 3 4 5 6 { 8 1 2 3 5 6 7 { 8 1 2 3 4 5 6 7 8 9 { 8Таким образом, каждая операция слияния серий требует n пересылок элементов, где n - общее число элементов серий. Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем слиять элементы со входных лент на выходную, пока какая-либо из них не опустеет. Затем она станет входной. Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии обозначены буквами fi, в таблице - количество элементов.
Число Фибоначчи порядка p определяются следующим образом: fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p, fp(p) = 1, fi(p) = 0 для 0 <= i < p. Очевидно, обычные числа Фибоначчи имеют порядок 1. Поэтому предположим существование фиктивных серий, таких что сумма фиктивных с реальными дает идеальное число. Сначала все данные располагаются на одной ленте. Лента читается и отрезки распределяются по другим лентам, имеющимся в системе. после того, как созданы начальные отрезки, они сливаются, как описано выше. Один из методов, который можно использовать для создания начальных отрезков, состоит в чтении порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут исчерпаны входные данные:
Начало файла - справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего.
Обратите внимание мы храним записи в буфере до тех пор, пока не наступит время записать их в выходной файл. Если вход случаен, средняя длина отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот метод, вообще говоря, более эффективен промежуточных, частичных сортировок. Прочитав из входного файла очередную запись, мы ищем наименьший ключ,
который >= последнего считанного. При этом мы, конечно, можем просто сканировать
записи в буфере. Однако, если таких записей тысячи, время поиска может
оказаться недопустимо большим. Если на этом этапе использовать двоичные
деревья, нам понадобится всего лишь lg n сравнений. Реализация.В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.![]() |