Реферат: Сортировка

1. ЛАБОРАТОРНАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ УЧЕНИКА 10д КЛАССА ШКОЛЫ N57

АХМАНОВА СЕРГЕЯ ПО ТЕМЕ "СОРТИРОВКИ".

2. ПОСТАНОВКА ЗАДАЧИ.

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

3. АЛГОРИТМ (метод решения).

Сначала исходный файл разбивается на куски по 10000 чисел, каждый кусок сортируется в памяти и записывается в один из двух временных файлов, причем так, что количество кусков в этих файлах отличается не более чем на 1(далее - первоначальная сортировка).

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

4. ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ.

При написании программы использовалась среда Borland Pascal 7.0 и встроенный компилятор.

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

Схема программы предельно проста: сначала выполняется первоначльная сортировка(процедура firstsort), затем вызываем склеивание(процедура ftrans(in1, in2, out1, out2: workfile);), где пары файлов все время меняются и после каждого запуска процедуры проверяется условие выхода.

Процедура ftrans открывает все файлы, затем выполняет несколько раз процедуру слива одного куска(onestep) и закрывает файлы.

5. КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ.

Модуль Files.

Сдесь переписаны все процедуры и функции необходимые для работы с файлами, работающие с блоками. Работа с ними осуществляется также как и с обычными процедурами модуля System.

unit Files;

interface

const typesize=4;

const bufsize = 2048;

type using=longint;

type buffer = array[1..bufsize] of using;

type pbuffer = ^buffer;

type filemode = (fread, fwrite, closed);

type tfile = record

buf: pbuffer;

mode: filemode;

f: file;

count, leng: integer;

end;

--> ЧИТАТЬ ПОЛНОСТЬЮ <--