Сортировка

1. ЛАБОРАТОРНАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ УЧЕНИКА 10д КЛАССА ШКОЛЫ N57 АХМАНОВА СЕРГЕЯ ПО ТЕМЕ СОРТИРОВКИ. 2. ПОСТАНОВКА ЗАДАЧИ. Дан файл, содержащий числа типа longint, расположенные в произвольном порядке. Требуется расположить эти числа по возрастанию, используя не более 40 килобайт оперативной памяти и дискового пространства не более чем в два раза больше исходного файла.

3. АЛГОРИТМ метод решения. Сначала исходный файл разбивается на куски по 10000 чисел, каждый кусок сортируется в памяти и записывается в один из двух временных файлов, причем так, что количество кусков в этих файлах отличается не более чем на 1далее - первоначальная сортировка. Затем, несколько раз выполняется операция склеиваниеодно выполнение операции склеивание мы будем незывать шаг, т.е два исходных файла, в которых находились отсортированные куски копируются в два других файла,

при этом из двух кусков, находящихся в разных файлах и имеющих одинаковые номера создается один отсортированный кусок. Этот кусок записывается в первый выходной файл если исходные куски имели нечетные номера и во второй, если исходные куски имели четные номера. 4. ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ. При написании программы использовалась среда Borland Pascal 7.0 и встроенный компилятор. Для ускоренного обмена с диском применялся блоковый ввод-

вывод, т.е информация читается и записывается целыми кластерами. Для осуществления этого способа ввода-вывода был написан модульFiles, с помощью которого ввод-вывод внешне не отличается от обычного. Схема программы предельно проста сначала выполняется первоначльная сортировкапроцедура firstsort, затем вызываем склеиваниепроцедура ftransin1, in2, out1, out2 workfile, где пары файлов все время меняются и после каждого запуска процедуры проверяется условие выхода.

Процедура ftrans открывает все файлы, затем выполняет несколько раз процедуру слива одного кускаonestep и закрывает файлы. 5. КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ. Модуль Files. Сдесь переписаны все процедуры и функции необходимые для работы с файлами, работающие с блоками. Работа с ними осуществляется также как и с обычными процедурами модуля System. unit Files interface const typesize4 const bufsize 2048 type usinglongint type buffer array1

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 fAssignvar w tfile name string procedure fReWritevar w tfile procedure fResetvar w tfile procedure fPutvar w tfile d using procedure fGetvar w tfile var d using procedure fClosevar w tfile function fEofvar w tfile boolean implementation procedure fAssignvar w tfile name string begin Assignw.f, name w.modeclosed end procedure fReWritevar w tfile begin if w.

modeclosed then begin ReWritew.f, typesize neww.buf w.count0 w.leng0 w.modefwrite end end procedure fResetvar w tfile begin if w.modeclosed then begin Resetw.f, typesize neww.buf BlockReadw.f, w.buf, bufsize, w.leng w.count1 w.modefread end end procedure fPutvar w tfile d using begin if w.modefwrite then begin w.countw.count1 w.bufw.countd if w.countbufsize then begin BlockWritew.f, w.buf, w.count w.count0 end end end procedure fGetvar w tfile var d using

begin if w.modefread then begin dw.bufw.count if w.lengw.count then begin BlockReadw.f, w.buf, bufsize, w.leng w.count1 end else w.countw.count1 end end procedure fClosevar w tfile begin if w.modefwrite then BlockWritew.f, w.buf, w.count disposew.buf w.modeclosed Closew.f end function fEofvar w tfile boolean begin if w.modefread and w.leng0 then fEoftrue else fEoffalse end begin end. конец files.pas Файл sort.pas - сортировка в памяти. var k integer function

SwapTopsno integer integer var t longint begin if memo2no1 memo2no then begin tmemono memonomemo2no1 memo2no1t SwapTops2no1 end else begin tmemono memonomemo2no memo2not SwapTops2no end end procedure SwapHalfno integer var t longint begin if memono memo2no then begin tmemono memonomemo2no memo2not end end function Regno integer boolean begin if 2no k then Regtrue else if 2no1 k then begin SwapHalfno Regtrue end else if memo2no memono and memo2no1 memono

then Regtrue else Regfalse end procedure HalfRegno integer var next integer begin nextno while not Regnext do nextSwapTopsnext end procedure RegTree var i integer begin for ik downto 1 do HalfRegi end procedure SwapLeavesl1, l2 integer var t longint begin tmemol1 memol1memol2 memol2t end procedure SortMemolen integer begin klen RegTree for klen-1 downto 1 do begin SwapLeaves1, k1 HalfReg1 end end конец sort.pas Основная пограмма uses

Dos, FilesПодключение модуля, осуществляющего ввод-вывод. const memlen10000Размер памяти, разрешенной для использования type tmemo array0 memlen of longint type pmemo tmemoТип-указатель на основной массив, используемый программой var memo pmemo I sort.pas Подключение файла, содержащего процедуру сортировки массива за время nlog n, не используя дополнительной памятисортировка деревом. type workfile record mainосновной файл, infфайл, содержащий длины отсортированных

кусков tfile endtfile - тип, определенный в unit Files, который заменяет файловые типы var t1, t2, t3, t4, dest, seur workfile временные файлы входной и выходной файл Инициализация procedure Init var tmp string begin tmpgetenvTEMP fAssignt1.main, tmpfsort-1.tmp fAssignt2.main, tmpfsort-2.tmp fAssignt3.main, tmpfsort-3.tmp fAssignt4.main, tmpfsort-4.tmp fAssignt1.inf, tmpfinf-1.tmp fAssignt2.inf, tmpfinf-2.tmp fAssignt3.inf, tmpfinf-3.tmp fAssignt4.inf, tmpfinf-4.tmp fAssignseur.main,

ParamStr1 fAssigndest.main,ParamStr2 end Первоначальная сортировка procedure firstsortvar inp, out1, out2 workfile var i, k longint begin fResetinp.main fRewriteout1.main fRewriteout2.main fRewriteout1.inf fRewriteout2.inf newmemo repeat for i1 to memlen do if fEofinp.main then begin ii-1 break end else fGetinp.main, memoi ki sortmemok for i1 to k do fPutout1.main, memoi fPutout1.inf, k if kmemlen then begin for i1 to memlen do if fEofinp.main then begin ii-1 break end else fGetinp.main, memoi ki sortmemok for

i1 to k do fPutout2.main, memoi fPutout2.inf, k end until fEofinp.main disposememo fCloseinp.main fCloseout1.main fCloseout2.main fCloseout1.inf fCloseout2.inf end Процедура, копирующая заданное количество эл-тов из одного файла в другой. Используется при сливании для копирования оставшейся части кускаесли другой кусок иссяк. procedure Copyvar inp, out workfile c0 longint var c, n longint Done boolean begin for cc0 downto 1 do begin fGetinp.main, n fPutout.main, n end end

Сливает два очередных куска из файлов in1 и in2 и записывает в out. procedure onestepvar in1, in2, out workfile c01, c02 longint var n1, n2, c1, c2, c longint Done boolean begin Donefalse c1c01-1 c2c02-1 c0 fGetin1.main, n1 fGetin2.main, n2 repeat if n1 n2 then begin fPutout.main, n1 cc1 if c10 then begin fPutout.main, n2 cc1 Copyin2, out, c2 ccc2 Donetrue end else begin fGetin1.main, n1 c1c1-1 end end else begin fPutout.main,

n2 cc1 if c20 then begin fPutout.main, n1 cc1 Copyin1, out, c1 ccc1 Donetrue end else begin fGetin2.main, n2 c2c2-1 end end until Done end Процедура осуществляет один шагт.е. копирует файлы in1 и in2 в out1 и out2, при этом склеивая куски procedure ftransvar in1,in2,out1,out2 workfile var c1, c2, c longint begin fResetin1.main fResetin2.main fResetin1.inf fResetin2.inf fRewriteout1.main fRewriteout2.main fRewriteout1.inf fRewriteout2.inf while

not fEofin1.inf and not fEofin2.inf do begin fGetin1.inf, c1 fGetin2.inf, c2 onestepin1, in2, out1, c1, c2 cc1c2 fPutout1.inf, c if not fEofin1.inf and not fEofin2.inf then begin fGetin1.inf, c1 fGetin2.inf, c2 onestepin1, in2, out2, c1, c2 cc1c2 fPutout2.inf, c end end if fEofin1.inf xor fEofin2.inf then if fEofin1.inf then begin fGetin2.inf, c2 Copyin2, out2, c2 fPutout2.inf, c2 end else if fEofin2.inf then begin fGetin1.inf, c1 Copyin1, out2, c1 fPutout2.inf, c1 end fClosein1.main fClosein2.main fClosein1.inf

fClosein2.inf fCloseout1.main fCloseout2.main fCloseout1.inf fCloseout2.inf end Копирование файла f1 в f2.Используется при завершении работы для копирования конечного файла из временной директории в указанную. procedure FCopyf1, f2 tfile var t longint begin writeкопирование fRewritef2 fResetf1 while not fEoff1 do begin fGetf1, t fPutf2, t end fClosef1 fClosef2 end Принимает значение True, если файл отсортирован и больше не надо склеивать.

Условие выхода function Fin boolean begin fResett2.main fResett4.main if fEoft2.main then begin Fintrue FCopyt1.main, dest.main end else if fEoft4.main then begin Fintrue FCopyt3.main, dest.main end else Finfalse fCloset2.main fCloset4.main end begin writeln if ParamCount 2 then begin writelnСлишком мало параметров. Exit end writeИнициализация Init writelnготово writeПервоначальная сортировка firstsortseur, t1, t2

writelnготово ReWritedest.main.f Closedest.main.f writelnСклеивание repeat ftranst1, t2, t3, t4 writelnшаг if not Fin then begin ftranst3, t4, t1, t2 writelnшаг end until Fin writelnготово end. 6. ВНЕШНЯЯ СПЕЦИФИКАЦИЯ. Для корректной работы программы необходим компьютер AT286, 40K свободной conventional памяти, операционная система MS-DOS 3.0 или более поздняя версия. Возможны версии программы, использующие меньше памяти, процессоры

слабее 286 и т.д. Программа использует место на диске вдвое большее исходного файлане считаяя сам файл. 7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ. При запуске программы обязательно должна быть определена переменная среды TEMP Формат запуска программы fsort.exe входной файл выходной файл Программа не задает ни каких вопросов, что сильно упрощает работу с ней. Результат работы можно поверить с помощью прилагаемой утилиты fcheck, создать случайный исходный файл

- с промощью fmake. Причинами ошибок могут служить не соответствие системы требованиям, изложенным в п. 6, недостаточное место на диске, размерв байтах исходного файла не кратен 4. В данном отчете описывается самая эфективная версия этой программы, но существуют версии, не использующие ввод-вывод блоками, требующие меньше ресурсов системы. 8. ОПИСАНИЕ ТЕСТОВ. Программма тестировалась неодноктатно, на входе использовались, в основном, файлы

из случайных чисел различной длины. На выходе были получены файлы тойже длины, не содержащие ошибок, т.е. числа в этох файлах оказались в порядке не строгого возрастания. Содержимое этих файлов полностью совпало с разультатами работы других программ сортировки на тех же входных файлах, что сильно снижает вероятность дифектов программы. При тестировании использовались операционные системы

MS-DOS 6.22, Windows95, компьютеры PC AT 486DX4-100, 486SX-25, работающие с локальным винчестером, робочие станции 486DX-40, 386SX, работающие в сети Novell. Результаты тестированияна файле размером 4M занесены в таблицу компьютер работа в сети время работы 486DX4-100 нет 3 мин. 486SX-25 нет 7 мин. 486DX-40 да 386SX да Форма отчета о лабораторной работе 1. ТИТУЛЬНЫЙ ЛИСТ.

Лабораторная работа ученика по теме 2. ПОСТАНОВКА ЗАДАЧИ. Описание решаемой задачи на естественном языке. 3. АЛГОРИТМ метод решения. Описание применяемого алгоритма на естественном языке, примерно в стиле, примененном в книге Программирование теоремы и задачи для объяснения сортировок. 4. ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ. Описание структуры программы - ее относительно независимых кусков

процедур, функций, модулей и интерфейса между ними например, какие параметры они друг другу передают и каков их содержательный смысл - в терминах, использованных в п.3. Использованный язык программирования. 5. КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ. Пункт может быть объединен с 4. 6. ВНЕШНЯЯ СПЕЦИФИКАЦИЯ. Требования программы к машине.

Обязательно ОС, использованная память можно написать работает под ДОС, используя только 640K, место на диске. 7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ. Как запустить программу, что отвечать на ее вопросы, как бороться с возникающими проблемами Пункт можно объединить с 6. 8. ОПИСАНИЕ ТЕСТОВ. Какие входные данные были использованы, каковы получены результаты, другие параметры работы в задаче сортировки, например - время работы.

9. ОГЛАВЛЕНИЕ. Для лабораторной работы не обязательно. Общий критерий таков любой незнакомый с задачей человек нормального интеллекта должен, имея ваш отчет и не задавая дополнительных вопросов, суметь запустить программу и разобраться, что она делает. Если он программирует на том же языке, он должен понять, как устроена программа.