Сортировка

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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Сортировка

Слов:1489
Символов:17081
Размер:33.36 Кб.