Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Сортировка

Название: Сортировка
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 18:42:07 09 апреля 2007 Похожие работы
Просмотров: 43 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:13:15 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
15:39:48 24 ноября 2015

Работы, похожие на Реферат: Сортировка

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150242)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru