Сортировка (лабораторная). : Информатика - на REFLIST.RU

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]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:=falo opАкЕ