АХМАНОВА СЕРГЕЯ ПО ТЕМЕ "СОРТИРОВКИ".
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;
procedure fAssign(var w: tfile; name: string);
procedure fReWrite(var w: tfile);
procedure fReset(var w: tfile);
procedure fPut(var w: tfile; d: using);
procedure fGet(var w: tfile; var d: using);
procedure fClose(var w: tfile);
function fEof(var w: tfile): boolean;
implementation
procedure fAssign(var w: tfile; name: string);
begin
Assign(w.f, name); w.mode:=closed;
end;
procedure fReWrite(var w: tfile); begin
if w.mode=closed then
begin
ReWrite(w.f, typesize); new(w.buf); w.count:=0; w.leng:=0; w.mode:=fwrite;
end;
end;
procedure fReset(var w: tfile); begin
if w.mode=closed then
begin
Reset(w.f, typesize); new(w.buf);
BlockRead(w.f, w.buf^, bufsize, w.leng); w.count:=1;
w.mode:=fread;
end;
end;
procedure fPut(var w: tfile; d: using);
begin
if w.mode=fwrite then
begin
w.count:=w.count+1;
w.buf^[w.count]:=d;
if w.count=bufsize then
begin
BlockWrite(w.f, w.buf^, w.count); w.count:=0;
end;
end;
end;
procedure fGet(var w: tfile; var d: using); begin
if (w.mode=fread) then
begin
d:=w.buf^[w.count];
if w.leng=w.count then
begin
BlockRead(w.f, w.buf^, bufsize, w.leng); w.count:=1;
end else w.count:=w.count+1;
end;
end;
procedure fClose(var w: tfile);
begin
if w.mode=fwrite then BlockWrite(w.f, w.buf^, w.count); dispose(w.buf);
w.mode:=closed;
Close(w.f); end;
function fEof(var w: tfile): boolean;
begin
if (w.mode=fread) and (w.leng=0) then fEof:=true
else fEof:=false;
end;
begin
end.
конец files.pas
----------------------------------------------------------------------------
Файл sort.pas - сортировка в памяти.
var k: integer;
function SwapTops(no: integer): integer;
var t: longint;
begin
if (memo^[2*no+1]>memo^[2*no]) then
begin
t:=memo^[no];
memo^[no]:=memo^[2*no+1];
memo^[2*no+1]:=t;
SwapTops:=2*no+1; end else begin
t:=memo^[no];
memo^[no]:=memo^[2*no];
memo^[2*no]:=t;
SwapTops:=2*no; end;
end;
procedure SwapHalf(no: integer);
var t: longint;
begin
if memo^[no]
begin
t:=memo^[no];
memo^[no]:=memo^[2*no];
memo^[2*no]:=t;
end;
end;
function Reg(no: integer): boolean;
begin
if (2*no)>k then Reg:=true else
if (2*no+1)>k then
begin
SwapHalf(no);
Reg:=true; end else
if (memo^[2*no]