Реферат Сортування

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 і: 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 і, 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

з, 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, з: 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, з: 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, з);

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, з);

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 так

Схожі реферати:

  • Реферат на тему: 5 різних завдань із програмування
    ДЕРЖАВНИЙ УНІВЕРСИТЕТ УПРАВЛІННЯ КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ КУРСОВАЯ РОБОТА з дисципліни
  • Реферат на тему: Теорія Попова
    рис. 1 рис. 2. рис. 3. рис.4. рис. 5. рис. 6. рис. 7. рис. 8. рис. 9. рис. 10. рис. 11.
  • Реферат на тему: Усе про Turbo Basic
    СТУДЕНТ! УВАГА! ЩОБ ПРОСМАТРИВАТЬ ЦЕЙ ФАЙЛ, ДОСТАТОЧНО, СТОЯ НА НЬОМУ, НАЖАТЬ КЛАВИШУ
  • Реферат на тему: Препроцессор мови З.
    ==================================================================== Зміст Запровадження 4 1.
  • Реферат на тему: Многопроцессорная обчислювальна система
    МНОГОПРОЦЕССОРНАЯ ОТКАЗОУСТОЙЧИВАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА 1 Призначення МВС Проектируемая МВС варта

Навігація