Рефераты. Лабораторная: Сортировка

Лабораторная: Сортировка

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] 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] 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 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 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 да