Сортировка
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]<=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
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 да