Алгоритм сбалансированного многопутевого слияния

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

Одним из наиболее эффективных алгоритмов внешней сортировки является алгоритм сбалансированного многопутевого слияния. Реализация классической версии этого алгоритма и явилась результатом моей работы.

1. Анализ задачи

сортировка программа перегруппировка

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

Рассмотрим некоторые основные понятия и допущения при работе с внешней памятью:

1. Операции чтения и записи на внешних устройствах дороже любых операций в памяти.

2. Различные технологии исполнения внешних устройств делают невозможными многие методы сортировок.

3. Последовательное чтение и запись - наиболее быстрый способ доступа к данным. Таким образом, в методах не будет использоваться произвольный доступ к данным (диски), а лишь последовательный доступ (ленты).

4. Работа с несколькими внешними устройствами, как правило, выполняется быстрее, чем работа только с одним устройством, т.к. имеется возможность параллельного использования устройств.

5. Эффективность сортировки определяется количеством копирований (последовательных операций чтения-записи) исходной информации.

6. Предполагается наличие N записей на одном внешнем устройстве для сортировки, внутренняя (оперативная) память, емкостью достаточной для хранения M записей, 2 внешних устройства для сортировки.

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

1. Последовательность «а» разбивается на 2 половины: «b» и «c».

2. Части «b» и «c» сливаются, при этом одиночные элементы образуют упорядоченные пары.

3. Полученная последовательность под именем а вновь обрабатывается в пунктах 1, 2; при этом упорядоченные пары переходят в такие же четверки.

4. Повторяя предыдущие шаги, сливаем четверки в восьмерки и т.д., каждый раз «удваивая» длину слитых подпоследовательностей до тех пор, пока не будет упорядочена целиком вся последовательность.

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

В случае прямого слияния мы не получаем никакого преимущества, если данные в начале уже частично упорядочены. Размер сливаемых на k-м проходе последовательностей меньше или равен 2^k и не зависит от существования более длинных уже упорядоченных подпоследовательностей, которые можно было бы просто объединить. Фактически любые две упорядоченные последовательности длиной m и n можно сразу сливать в одну последовательность из m+n элементов. Сортировка, при которой сливаются две самые длинные из последовательностей, называется естественным слиянием.

Упорядоченные последовательности часто называют строками. Однако, так как слово «строка» ещё чаще употребляется для названия последовательности символов, то мы для упорядоченных последовательностей будем использовать термин «серия». Таким образом, подпоследовательность , удовлетворяющих условию:

,

называется максимальной серией. Поэтому при сортировке слиянием объединяются (максимальные) серии, а не последовательности, заранее фиксированной длины. Если сливаются последовательности из n серий, то результирующая содержит опять ровно n серий. Следовательно, при каждом проходе общее число серий уменьшается вдвое, и общее число пересылок в самом плохом случае равно n*[log(n)], а в среднем даже меньше. Ожидаемое число сравнений значительно больше, поскольку кроме сравнений, необходимых для отбора элементов при слиянии, нужны ещё дополнительные - между последовательными элементами каждого файла, чтобы определить конец серии.

2. Алгоритм сбалансированного многопутевого слияния

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

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

В данной курсовой работе рассматривается сбалансированное много путевое слияние.

Сбалансированное много путевое слияние можно считать частным случаем естественного слияния (в случае его однофазной формулировки). Т.е. сбалансированное многопутевое слияние дает существенное преимущество, если данные в начале уже частично упорядочены, по сравнению с прямым слиянием.

Затраты на любую последовательную сортировку пропорциональны числу требуемых проходов, так как по определению при каждом из проходов копируются все данные. Один из способов сократить это число - распределять серии более чем в две последовательности. Слияние r серий распределенных в N последовательностей даст в результате r/N серий. Второй проход уменьшит это число до серий, третий - до и т.д., после k проходов останется серий. Поэтому общее число проходов, необходимых для сортировки n элементов с помощью N-путевого слияния, равно K = [log_Nn]. Поскольку при каждом проходе выполняется n операций копирования, то в самом плохом случае понадобится M = n*[log_Nn] таких операций.

2.1 Основные этапы сортировки сбалансированным многопутевым слиянием

1. Начальное распределение. Во время этого шага исходная информация считывается кусками по M записей во внутреннюю память и сортируется (при условии, что такое количество памяти имеется). После сортировки кусок памяти в M записей записывается на первый файл. Далее процесс продолжается, запись отсортированного куска производится на второй файл, затем в третье и т.д. до P. Таким образом, в блок записано P*M записей. Далее процесс продолжается, начиная с первого файла до сортировки кусками по M записей всего исходного файла.

2. Слияние. Во время этого шага с P файлов берётся по одной записи в некоторый массив, и наименьшая из них записывается в (P+1) файл. После чего, массив дополняется записью с того устройства, с которого была прочитана, только что записанная запись. Продолжая процесс таким образом, получаем M*P записей отсортированных в P файле (сортировка слиянием). Следующие M*P записей сортируются в (P+2) файле. В итоге получаем P кусков, размером в M*P, отсортированных в P файлах (P+1, P+2,…, 2P).

3. Обмен. На этом шаге обмениваем первый массив P файлов (1, 2,…, P) со вторым массивом (P+1, P+2,…, 2P). Повторяем шаги 2-3 до тех пор, пока не будет отсортирован входной файл.

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

2.2 Способы формирования начальных отрезков

1. Из файла в оперативную память переносится определенное число записей и упорядочивается одним из методов внутренней сортировки. У этого способа есть и достоинства и недостатки.

Достоинство: Независимо от входного набора данных, все отрезки имеют одинаковую длину, что упрощает алгоритм слияния.

Недостатком такого метода является то, что невозможно сформировать более длинные отрезки, чем позволяет оперативная память.

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

3. Описание структуры программы

В начале работы программы создается файл, который нужно будет сортировать. Содержимое файла представляет собой записи размером SORT_REC_LENGTH = 200 байт. Первые 6 байт отведены под значение ключа, а остальные представляют собой символы алфавита. Структура этой записи имеет вид: TSortRec = String [SORT_REC_LENGTH]. Это не самый правильный вариант представления. Правильнее было бы так:

type

TSortRec = packed record

Key: LongInt;

Data: array [1..SORT_REC_LENGTH - 4] of Byte;

end;

Однако выбранное в программе представление записи позволяет наглядно убедиться в правильности сортировки. Для этого достаточно просмотреть в блокноте файл Result.txt. После того, как файл сформирован, создаются три его копии, т.к. мы должны тестировать три метода начального формирования отрезков с последующим, сбалансированным многопутевым слиянием. Затем вызывается функция начального формирования отрезков SimpleDistribute, параметрами которой являются файл, который следует отсортировать и число путей слияния (WaysCount). SimpleDistribute возвращает количество операций копирования, а точнее возвращает «0», т.к. в этой процедуре не происходило операций копирования. Смысл этой функции заключается в том, что необходимо распределить наш сортируемый файл по нескольким последовательностям, т.к. BalancedMergeSort работает сразу с несколькими последовательностями. Разделение происходит следующим образом, мы считываем из сортируемого файла запись и помещаем в файл, следующая запись помещается в следующий файл и т.д., когда происходит запись в последний файл, то происходит переключение на первый файл, т.е. мы двигаемся по кругу до тех пор, пока не кончится входной файл.

Затем вызывается функция BalancedMergeSort, параметрами которой является число путей слияния. Эта функция возвращает, в качестве результата, следующую структуру TsortReport. Эта структура была создана для вывода результатов работы алгоритма и имеет вид:

TSortReport = record

TimeWorked: Integer;

StepsCount: Integer;

CopyCount: Integer;

end;

Поле TimeWorked отвечает за время работы алгоритма, StepsCount - количество проходов, CopyCount - количество операций копирования.

В самой процедуре используются следующие структуры:

TSortFile = File of TSortRec;

F: array [0..1, 0..MAX_WAYS_COUNT - 1] of TSortFile;

Файловые переменные массивов F[0] и F[1] указывают на входные и выходные последовательности.

CurRec: array [0..MAX_WAYS_COUNT - 1] of TSortRec;

Массив содержит для каждого входного файла последнюю считанную запись.

SegFinished: array [0..MAX_WAYS_COUNT - 1] of Boolean;

Элемент массива равен False, если текущий отрезок входной последовательности закончился, иначе он равен True.

SegLength: array [0..MAX_WAYS_COUNT - 1] of Integer;

Массив содержит прочитанную длину отрезка

Empty: array [0..MAX_WAYS_COUNT - 1] of Boolean;

Элемент массива равен True, если входная последовательность закончилась, иначе он равен False.

Сначала инициализируем входную и выходную последовательности файлов. Затем входим в бесконечный цикл. Считываем в массив CurRec элементы с файлов, переменная T отвечает за количество считанных последовательностей. В случае, если элемент считан из i-го файла, i-му элементу массива Empty присваивается значение истины. Условием выхода из цикла является значение T<=1, т.е. осталась одна последовательность - отсортированная. Далее находим минимальный элемент среди первых элементов отрезков, точнее его индекс. Выводим минимальный элемент в очередную выходную последовательность и проверяем, закончилась последовательность или нет. Если нет, то считываем очередную запись и проверяем меньше ли она предыдущей, если да, то отрезок закончился, иначе записываем его в наш массив. Если файл, из которого считали отрезок пуст, то уменьшаем количество не пустых последовательностей. Если же считанные отрезки закончились, то переключаемся на следующий файл. Если закончились все входные файлы, то меняем местами входные и выходные файлы.

Так же в данной курсовой работе применяются алгоритм сортировки разделением и пирамидальной сортировки.

Алгоритм сортировки методом разделения состоит из следующих шагов:

1. из массива выбирается некоторый опорный элемент a[i].

2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо.

3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого (Рисунок 1).

Рисунок 1

4. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.

На входе массив a[0]… a[N] и опорный элемент p, по которому будет производиться разделение.

1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.

2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p.

3. Далее, если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i, j по тем же правилам…

4. Повторяем шаг 3, пока i <= j.

Рассмотрим работу процедуры для массива a[0]… a[6] и опорного элемента p = a[3] (Рисунок 2).



Рисунок 2 - Пример работы сортировки с разделением

Алгоритм пирамидальной сортировки.

Структура данных:

H-массив для пирамиды.

m-размер пирамиды.

mh=m/2-середина пирамиды.

L, R-используются как индексы ограничивающие пирамиду.

?исходный файл.

?куда производится копирование.

-первый элемент.

Массив H одновременно содержит две пирамиды, нижнюю и верхнюю. На выход подаётся нижняя пирамида.

В общем случае нижняя (текущая) пирамида состоит из элементов H[1], H[2],…, H[L], а верхняя ? из H [L + 1], H [L + 2],…, H[N].

Пирамидальная сортировка состоит из следующих шагов:

1. Чтение первых элементов с входа и размещение их в верхней половине пирамиды, где не требуется упорядоченности ключей.

2. Чтение следующих элементов и расстановка их в нижней части пирамиды.

3. Необходимо переупорядовачивание ключей такое же что и при построении пирамиды.

L=m и для всех оставшихся элементов повторяются следующие шаги:

3.1. h1 - пересылается в соответствующую выходную последовательность

3.2 Если ключ h1следующий элемент входной последовательности, то этот элемент принадлежит тому же отрезку и его можно просеять на соответствующие место (переформирование пирамиды с новым ключом и неизменными размерами от 1…L).

3.3. В противном случае сократить размер пирамиды (переформировать с уменьшением размера от L). И поместить новый элемент во вторую верхнюю пирамиду, которая строится для следующего отрезка. Границей между пирамидами является индекс L.

4. Входные данные исчерпаны. Задаем значение правой границы R=m. Сбрасываем нижнюю пирамиду. Строится верхняя пирамида и постепенно смешается на позицию H [L + 1], H[R].

5. В массиве остается одна пирамида, занимающая позицию от 1…R. Она формирует последний отрезок (копирование элементов в файл происходит с уменьшением R).

4. Результаты проведенных испытаний

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

Например, если использовать стратегию просеивания через пирамиду, то время работы программы уменьшается 3,4 раза, количество проходов - 2,7 раза, количество операции копирования - 3,4 раза (Рисунок 3).

Рисунок 3 - Пример работы программы

Таблица 1 - Результаты экспериментов

Количество путей слияния	Метод	Вычислительная сложность	Средняя длина отрезков	Количество отрезков	Время работы сортировки, мс	Количество проходов	Количество операций копирования
2	Простой метод	0	1	5028	3610	14	130000
	QSort	79885	1000	10	1109	5	40000
	HeapSort	95630	1666	6	985	4	30000
3	Простой метод	0	2	4947	2375	9	80000
	QSort	78868	1000	10	813	4	30000
	HeapSort	95981	1666	6	578	3	20000
4	Простой метод	0	1	5003	2135	8	70000
	QSort	79297	1000	10	828	3	20000
	HeapSort	95983	1666	6	1140	3	20000
5	Простой метод	0	2	4993	2141	7	60000
	QSort	79657	1000	10	719	3	20000
	HeapSort	95820	1666	6	812	3	20000
6	Простой метод	0	1	5044	1516	6	50000
	QSort	79711	1000	10	609	3	20000
	HeapSort	95935	1666	6	312	2	10000
7	Простой метод	0	2	4944	1578	6	50000
	QSort	79699	1000	10	625	3	20000
	HeapSort	95769	1666	6	329	2	10000
8	Простой метод	0	1	5049	1766	6	50000
	QSort	79438	1000	10	687	3	20000
	HeapSort	95896	1666	6	391	2	10000
9	Простой метод	0	2	4985	1375	5	40000
	QSort	79528	1000	10	687	3	20000
	HeapSort	95732	1666	6	328	2	10000
10	Простой метод	0	2	4997	1406	5	40000
	QSort	79183	1000	10	391	2	10000
	HeapSort	95755	1666	6	344	2	10000

Наиболее высокие результаты сортировка сбалансированным многопутевым слиянием без стратегии начального формирования показывает при количестве путей слияния от 4 до 6.

Заключение

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

Список используемой литературы

1. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989 г.

2. Кнут Д. «Искусство программирования для ЭВМ», т. 3

«Сортировка и поиск». М.: Мир, 1978 г.

3. Лорин Г. «Сортировка и системы сортировки». М.: Наука, 1983 г.

4. М. Сибуя, Т. Ямамото «Алгоритмы обработки данных». М.: Мир, 1986 г.

Приложение

Листинг программы

unit BalancedSort;

interface

Uses SortStruct;

type

TSortReport = record

TimeWorked: Integer;

StepsCount: Integer;

CopyCount: Integer;

end;

function BalancedMergeSort (WaysCount: Integer): TSortReport;

implementation

Uses Windows, SysUtils;

function BalancedMergeSort (WaysCount: Integer): TSortReport;

var

F: array [0..1, 0..MAX_WAYS_COUNT - 1] of TSortFile;

CurRec: array [0..MAX_WAYS_COUNT - 1] of TSortRec;

SegFinished: array [0..MAX_WAYS_COUNT - 1] of Boolean;

Empty: array [0..MAX_WAYS_COUNT - 1] of Boolean;

X: TSortRec;

T, M, i, j, k: Integer;

begin

Result. TimeWorked:=GetTickCount();

Result. StepsCount:=0;

Result. CopyCount:=0;

For k:=0 to 1 do

For i:=0 to WaysCount - 1 do

AssignFile (F[k] [i], IntToStr(k) + IntToStr(i) + '.tmp');

k:=0;

While True do

begin

inc (Result. StepsCount);

For i:=0 to WaysCount - 1 do

begin

Reset (F[k] [i]);

ReWrite (F[1 - k] [i]);

end;

T:=0;

For i:=0 to WaysCount - 1 do

If not Eof (F[k] [i]) then

begin

inc(T);

Empty[i]:=False;

Read (F[k] [i], CurRec[i]);

end

else

Empty[i]:=True;

If T <= 1 then Break;

j:=0;

While T > 0 do

begin

For i:=0 to WaysCount - 1 do

SegFinished[i]:=Empty[i];

While True do

begin

M:=-1;

For i:=0 to WaysCount - 1 do

If not SegFinished[i] and ((M = -1) or (RecCmp (CurRec[i], CurRec[M]) < 0))

then M:=i;

If M = -1 then Break;

Write (F[1 - k] [j], CurRec[M]);

inc (Result. CopyCount);

If not Eof (F[k] [M]) then

begin

Read (F[k] [M], X);

If RecCmp (X, CurRec[M]) < 0 then

SegFinished[M]:=True;

CurRec[M]:=X;

end

else

begin

SegFinished[M]:=True;

Empty[M]:=True;

dec(T);

end;

end;

j:=(j + 1) mod WaysCount;

end;

k:=1 - k;

end;

Result. TimeWorked:=Integer (GetTickCount()) - Result. TimeWorked;

CopyFile (PChar(IntToStr(k) + '0.tmp'), PChar ('Result.txt'), False);

For k:=0 to 1 do

For i:=0 to WaysCount - 1 do

begin

CloseFile (F[k] [i]);

Erase (F[k] [i]);

end;

end;

end.

unit SegmentDistribute;

interface

Uses SortStruct;

type

TDistribReport = record

Difficulty: Integer;

AvrSegLength: Integer;

SegCount: Integer;

end;

function SimpleDistribute (const FileName: String; WaysCount: Integer): TDistribReport;

function QSortDistribute (const FileName: String; WaysCount: Integer): TDistribReport;

function HeapDistribute (const FileName: String; WaysCount: Integer): TDistribReport;

implementation

Uses SysUtils;

var

F: TSortFile;

SF: array [0..MAX_WAYS_COUNT - 1] of TSortFile;

A: array [1..MEM_REC_COUNT] of TSortRec;

function SimpleDistribute (const FileName: String; WaysCount: Integer): TDistribReport;

var

i: Integer;

CurRec: TSortRec;

Empty: array [0..MAX_WAYS_COUNT - 1] of Boolean;

LastRec: array [0..MAX_WAYS_COUNT - 1] of TSortRec;

begin

Reset (F, FileName);

For i:=0 to WaysCount - 1 do

ReWrite (SF[i], '0' + IntToStr(i) + '.tmp');

Result. SegCount:=0;

FillChar (Empty, SizeOf(Empty), True);

i:=0;

While not Eof(F) do

begin

Read (F, CurRec);

Write (SF[i], CurRec);

If Empty[i] or (GetKey(CurRec) < GetKey (LastRec[i])) then

begin

inc (Result. SegCount);

Empty[i]:=False;

end;

LastRec[i]:=CurRec;

i:=(i + 1) mod WaysCount;

end;

Result. AvrSegLength:=FileSize(F) div Result. SegCount;

For i:=0 to WaysCount - 1 do

CloseFile (SF[i]);

CloseFile(F);

Result. Difficulty:=0;

end;

function QSort (Left, Right: Integer): Integer;

X: TSortRec;

i, j: LongInt;

begin

Result:=0;

i:=Left;

j:=Right;

X:=A[(Left + Right) div 2];

Repeat

While (RecCmp (A[i], X) < 0) do

inc(i);

While (RecCmp (A[j], X) > 0) do

dec(j);

If (i < j) then

begin

Swap (A[i], A[j]);

inc (Result, 3);

end;

If (i <= j) then

begin

inc(i);

dec(j);

end;

until i >= j;

If Left < j then inc (Result, QSort (Left, j));

If i < Right then inc (Result, QSort (i, Right));

end;

function QSortDistribute (const FileName: String; WaysCount: Integer): TDistribReport;

var

N, i, j: LongInt;

CurRec: TSortRec;

begin

Result. Difficulty:=0;

Result. SegCount:=0;

Reset (F, FileName);

For i:=0 to WaysCount - 1 do

ReWrite (SF[i], '0' + IntToStr(i) + '.tmp');

i:=0;

While not Eof(F) do

begin

N:=0;

While not Eof(F) and (N < MEM_REC_COUNT) do

begin

Read (F, CurRec);

inc(N);

A[N]:=CurRec;

inc (Result. Difficulty);

end;

inc (Result. Difficulty, QSort (1, N));

inc (Result. SegCount);

For j:=1 to N do

Write (SF[i], A[j]);

i:=(i + 1) mod WaysCount;

end;

Result. AvrSegLength:=FileSize(F) div Result. SegCount;

For i:=0 to WaysCount - 1 do

CloseFile (SF[i]);

CloseFile(F);

end;

function Heap (Root: Integer; Key: TSortRec; Bound: Integer): Integer;

var

vc, lch: Integer;

begin

Result:=0;

vc:=Root;

While vc * 2 <= Bound do

begin

lch:=vc * 2;

If (lch < Bound) and (RecCmp (A[lch], A [lch + 1]) > 0) then

inc(lch);

If (RecCmp (Key, A[lch]) < 0) then

Break

else

begin

A[vc]:=A[lch];

inc(Result);

vc:=lch;

end;

end;

A[vc]:=Key;

inc(Result);

end;

function HeapDistribute (const FileName: String; WaysCount: Integer): TDistribReport;

var

X: TSortRec;

L, M, R, mh, i: Integer;

begin

Reset (F, FileName);

If (FileSize(F) < MEM_REC_COUNT) then

begin

CloseFile(F);

Result:=QSortDistribute (FileName, WaysCount);

Exit;

end;

For i:=0 to WaysCount - 1 do

ReWrite (SF[i], '0' + IntToStr(i) + '.tmp');

Result. Difficulty:=0;

Result. SegCount:=0;

M:=MEM_REC_COUNT;

mh:=M div 2;

L:=M;

Repeat

Read (F, A[L]);

dec(L);

until L = mh;

Repeat

Read (F, X);

inc (Result. Difficulty, Heap (L, X, M));

dec(L);

until L = 0;

L:=M;

i:=0;

While not Eof(F) do

begin

Write (SF[i], A[1]);

Read (F, X);

If RecCmp (A[1], X) <= 0 then

inc (Result. Difficulty, Heap (1, X, L))

else

begin

inc (Result. Difficulty, Heap (1, A[L], L - 1));

If L > mh then

begin

A[L]:=X;

inc (Result. Difficulty);

end

else

inc (Result. Difficulty, Heap (L, X, M));

dec(L);

If L = 0 then

begin

inc (Result. SegCount);

L:=M;

i:=(i + 1) mod WaysCount;

end;

end;

end;

If L > 0 then

inc (Result. SegCount);

R:=M;

Repeat

Write (SF[i], A[1]);

inc (Result. Difficulty, Heap (1, A[L], L - 1));

If L > mh then

begin

A[L]:=A[R];

inc (Result. Difficulty);

end

else

inc (Result. Difficulty, Heap (L, A[R], R - 1));

dec(L);

dec(R);

until L = 0;

If R > 0 then // Если R > 0,

inc (Result. SegCount);

i:=(i + 1) mod WaysCount;

While R > 0 do

begin

Write (SF[i], A[1]);

inc (Result. Difficulty, Heap (1, A[R], R - 1));

dec(R);

end;

Result. AvrSegLength:=FileSize(F) div Result. SegCount;

For i:=0 to WaysCount - 1 do

CloseFile (SF[i]);

CloseFile(F);

end;

end.

unit SortStruct;

interface

const

MAX_WAYS_COUNT = 10;

SORT_REC_LENGTH = 200;

SORT_KEY_LENGTH = 6;

MEM_REC_COUNT = 1000;

type

TSortRec = String [SORT_REC_LENGTH];

TSortFile = File of TSortRec;

function GetKey (const A: TSortRec): Integer;

function RecCmp (const A, B: TSortRec): Integer;

procedure Swap (var A, B: TSortRec);

function GenRandom: TSortRec;

implementation

Uses SysUtils;

function GetKey (const A: TSortRec): Integer;

begin

Result:=StrToInt (Copy(A, 1, SORT_KEY_LENGTH));

end;

function RecCmp (const A, B: TSortRec): Integer;

begin

Result:=GetKey(A) - GetKey(B);

end;

procedure Swap (var A, B: TSortRec);

var

C: TSortRec;

begin

C:=A;

A:=B;

B:=C;

end;

function GenRandom: TSortRec;

var

j: LongInt;

begin

Result:='';

For j:=1 to SORT_KEY_LENGTH do

Result:=Result + Chr (Random(10) + Ord('0'));

For j:=1 to SORT_REC_LENGTH - SORT_KEY_LENGTH do

Result:=Result + Chr (Random(26) + Ord('A'));

end;

end.

Размещено на Allbest.ru