Сортировка

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;

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]<memo^[2*no] then

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]<=memo^[no]) and (memo^[2*no+1]<=memo^[no]) then Reg:=true

Else Reg:=false;

End;

Procedure HalfReg(no: integer);

Var next: integer;

Begin

Next:=no;

While (not Reg(next)) do next:=SwapTops(next);

End;

Procedure RegTree;

Var i: integer;

Begin

For i:=k downto 1 do HalfReg(i);

End;

Procedure SwapLeaves(l1, l2: integer);

Var t: longint;

Begin

T:=memo^[l1];

Memo^[l1]:=memo^[l2];

Memo^[l2]:=t;

End;

Procedure SortMemo(len: integer);

Begin

K:=len;

RegTree;

For k:=len-1 downto 1 do

Begin

SwapLeaves(1, k+1);

HalfReg(1); end;

End;

Конец sort. pas

—————————————————————————-

Основная пограмма

Uses Dos, FilesПодключение модуля, осуществляющего ввод-вывод.;

Const memlen=10000;Размер памяти, разрешенной для использования

Type tmemo = array[0 .. memlen] of longint;

Type pmemo = ^ tmemo;Тип-указатель на основной массив, используемый

Программой

Var memo : pmemo;

$I sort. pas Подключение файла, содержащего процедуру сортировки

Массива за время n*(log n), не используя дополнительной памяти(сортировка

Деревом).

Type workfile = record

Mainосновной файл,

Infфайл, содержащий длины отсортированных кусков: tfile;

End;tfile – тип, определенный в unit Files, который заменяет файловые типы

Var

T1, t2, t3, t4, dest, seur: workfile;

Временные файлы входной и выходной файл

Инициализация

Procedure Init;

Var tmp: string;

Begin

Tmp:=getenv(‘TEMP’);

FAssign(t1.main, tmp+’\~fsort-1.tmp’);

FAssign(t2.main, tmp+’\~fsort-2.tmp’);

FAssign(t3.main, tmp+’\~fsort-3.tmp’);

FAssign(t4.main, tmp+’\~fsort-4.tmp’);

FAssign(t1.inf, tmp+’\~finf-1.tmp’);

FAssign(t2.inf, tmp+’\~finf-2.tmp’);

FAssign(t3.inf, tmp+’\~finf-3.tmp’);

FAssign(t4.inf, tmp+’\~finf-4.tmp’);

FAssign(seur. main, ParamStr(1));

FAssign(dest. main, ParamStr(2));

End;

Первоначальная сортировка

Procedure firstsort(var inp, out1, out2: workfile);

Var i, k: longint;

Begin

FReset(inp. main);

FRewrite(out1.main);

FRewrite(out2.main);

FRewrite(out1.inf);

FRewrite(out2.inf);

New(memo);

Repeat

For i:=1 to memlen do

If fEof(inp. main) then

Begin

I:=i-1;

Break

End else fGet(inp. main, memo^[i]);

K:=i;

Sortmemo(k);

For i:=1 to k do fPut(out1.main, memo^[i]);

FPut(out1.inf, k);

If k=memlen then

Begin

For i:=1 to memlen do

If fEof(inp. main) then

Begin

I:=i-1;

Break;

End

Else fGet(inp. main, memo^[i]);

K:=i;

Sortmemo(k);

For i:=1 to k do fPut(out2.main, memo^[i]);

FPut(out2.inf, k);

End;

Until fEof(inp. main);

Dispose(memo);

FClose(inp. main);

FClose(out1.main);

FClose(out2.main);

FClose(out1.inf);

FClose(out2.inf);

End;

Процедура, копирующая заданное количество эл-тов из одного файла в другой.

Используется при сливании для копирования оставшейся части куска(если другой кусок иссяк).

Procedure Copy(var inp, out: workfile; c0: longint);

Var

C, n: longint;

Done: boolean; begin

For c:=c0 downto 1 do begin

FGet(inp. main, n); fPut(out. main, n);

End;

End;

Сливает два очередных куска из файлов in1 и in2 и записывает в out. procedure onestep(var in1, in2, out: workfile; c01, c02: longint); var n1, n2, c1, c2, c: longint;

Done: boolean; begin

Done:=false; c1:=c01-1; c2:=c02-1; c:=0; fGet(in1.main, n1); fGet(in2.main, n2); repeat

If n1<n2 then begin

FPut(out. main, n1); c:=c+1; if c1=0 then begin

FPut(out. main, n2); c:=c+1; Copy(in2, out, c2); c:=c+c2; Done:=true;

End else

Begin

FGet(in1.main, n1); c1:=c1-1;

End;

End else

Begin

FPut(out. main, n2);

C:=c+1;

If c2=0 then

Begin

FPut(out. main, n1);

C:=c+1;

Copy(in1, out, c1); c:=c+c1; Done:=true;

End else

Begin

FGet(in2.main, n2); c2:=c2-1;

End;

End;

Until Done;

End;

Процедура осуществляет один шаг(т. е. копирует файлы in1 и in2 в out1 и out2, при этом склеивая куски)

Procedure ftrans(var in1,in2,out1,out2: workfile);

Var c1, c2, c: longint;

Begin

FReset(in1.main);

FReset(in2.main);

FReset(in1.inf);

FReset(in2.inf);

FRewrite(out1.main);

FRewrite(out2.main);

FRewrite(out1.inf);

FRewrite(out2.inf);

While (not fEof(in1.inf)) and (not fEof(in2.inf)) do

Begin

FGet(in1.inf, c1);

FGet(in2.inf, c2);

Onestep(in1, in2, out1, c1, c2);

C:=c1+c2;

FPut(out1.inf, c);

If (not fEof(in1.inf)) and (not fEof(in2.inf)) then

Begin

FGet(in1.inf, c1);

FGet(in2.inf, c2);

Onestep(in1, in2, out2, c1, c2);

C:=c1+c2;

FPut(out2.inf, c);

End;

End;

If fEof(in1.inf) xor fEof(in2.inf) then

If fEof(in1.inf) then

Begin

FGet(in2.inf, c2);

Copy(in2, out2, c2); fPut(out2.inf, c2);

End else

If fEof(in2.inf) then begin

FGet(in1.inf, c1); Copy(in1, out2, c1); fPut(out2.inf, c1);

End; fClose(in1.main); fClose(in2.main); fClose(in1.inf); fClose(in2.inf); fClose(out1.main); fClose(out2.main); fClose(out1.inf); fClose(out2.inf);

End;

Копирование файла f1 в f2.(Используется при завершении работы для

Копирования конечного файла из временной директории в указанную).

Procedure FCopy(f1, f2: tfile);

Var t: longint;

Begin

Write(‘копирование’);

FRewrite(f2);

FReset(f1);

While (not fEof(f1)) do

Begin

FGet(f1, t);

FPut(f2, t);

End;

FClose(f1);

FClose(f2);

End;

Принимает значение True, если файл отсортирован и больше не надо склеивать.

(Условие выхода)

Function Fin: boolean;

Begin

FReset(t2.main);

FReset(t4.main);

If fEof(t2.main) then

Begin

Fin:=true;

FCopy(t1.main, dest. main); end else

If fEof(t4.main) then

Begin

Fin:=true;

FCopy(t3.main, dest. main); end else Fin:=false; fClose(t2.main); fClose(t4.main);

End;

Begin

Writeln;

If ParamCount<2 then

Begin

Writeln(‘Слишком мало параметров.’);

Exit; end; write(‘Инициализация…’); Init; writeln(‘готово’); write(‘Первоначальная сортировка…’); firstsort(seur, t1, t2); writeln(‘готово’); ReWrite(dest. main. f); Close(dest. main. f); writeln(‘Склеивание:’); repeat

Ftrans(t1, t2, t3, t4);

Writeln(‘шаг’);

If (not Fin) then

Begin

Ftrans(t3, t4, t1, t2);

Writeln(‘шаг’);

End;

Until Fin;

Writeln(‘готово’);

End.

—————————————————————————-

6. ВНЕШНЯЯ СПЕЦИФИКАЦИЯ.

Для корректной работы программы необходим компьютер AT286, 40K свободной conventional памяти, операционная система MS-DOS 3.0 или более поздняя версия. Возможны версии программы, использующие меньше памяти, процессоры слабее 286 и т. д. Программа использует место на диске вдвое большее исходного файла(не считаяя сам файл).

7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ.

При запуске программы обязательно должна быть определена переменная среды TEMP!

Формат запуска программы:

F_sort[.exe] <входной файл> <выходной файл>

Программа не задает ни каких вопросов, что сильно упрощает работу с ней.

Результат работы можно поверить с помощью прилагаемой утилиты f_check, создать случайный исходный файл – с промощью f_make.

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

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

8. ОПИСАНИЕ ТЕСТОВ.

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

При тестировании использовались операционные системы MS-DOS 6.22, Windows’95, компьютеры PC AT 486DX4-100, 486SX-25, работающие с локальным винчестером, робочие станции 486DX-40, 386SX, работающие в сети Novell.

Результаты тестирования(на файле размером 4M) занесены в таблицу: компьютер работа в сети время работы

486DX4-100 нет 3 мин.

486SX-25 нет 7 мин.

486DX-40 да

386SX да


Сортировка