Изучение методов сортировки

Лабораторная работа № 10

ОСНОВЫ ПРОГРАММИРОВАНИЯ В СИСТЕМЕ

TURBO PASCAL.

РАБОТА С ГЛАВНЫМ МЕНЮ СИСТЕМЫ.

ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ МАССИВОВ.

МЕТОДЫ СОРТИРОВКИ

Цель:

Изучить команды режима OPTIONS (до ENVIROMENT) среды Turbo Pascal версии 7.0. Усвоить правила работы с переменными типа массив языка программирования Pascal. Изучить методы сортировки. Приобрести дальнейшие навыки по отладке программ.

Общие сведения

Меню опции OPTIONS

COMPILER. Эта опция задает несколько параметров, с помощью которых Вы можете управлять генерацией машинного кода программы.

Опция Force far calls определяет генерацию машинного кода, рассчитанного на дальнюю модель памяти. В соответствии с архитектурой центральнoгo процессора ПК могут использоваться две модели вызова процедур и функций: ближняя (NEAR) и дальняя (FAR). Ближняя модель обеспечивает адресацию в пределах текущего сегмента, дальняя используется для организации межсегментных связей. Если опция установлена в активное состояние, все вызовы процедур и функций будут использовать дальнюю (межсегментную) модель, в противном случае - ближнюю (внутрисегментную) модель. Ближняя модель дает более экономный код программы и исполняется быстрее, однако при организации оверлея и вызова из программы других программ с помощью процедуры EXEC нужно использовать дальнюю модель.

При активном состоянии опции Overlays allowed компилятор генерирует дополнительный код при компиляции оверлейных модулей. Этот код позволяет передавать строки и множества в качестве фактических параметров при обращении из одного оверлейного модуля в другой. Отметим, что Турбо Паскаль считает модуль оверлейным только в том случае, когда он откомпилирован с активной опцией Overlays allowed.

Опция Word align data определяет способ выравнивания переменных и констант в памяти: если опция активна, каждая переменная и константа начинается в байте с четным адресом, т.е. выравнивается на начало машинного слова, если неактивна, переменные и константы располагаются в памяти сплошной цепочкой. Выравнивание по словом увеличивает скорость выполнения программ ценой несколько неэкономного расходования памяти.

Активною состояние опции 286 instructions предписывает компилятору создавать код программы с полным набором команд микропроцессора Intel 80286. В неактивном состоянии опции компилятор порождает код, соответствующий набору команд микропроцессора Intel 8088 и представляющий собой подмножество команд микропроцессора Intel 80386. В целях переносимости программ имеет смысл устанавливать неактивное состояние этой опции, так как в процессе счета программа не проверяет фактическое наличие микропроцессора Intel 30286 и не может эмулировать его систему команд.

В активном состоянии опции Range checking генерируется дополнительный код для проверки возможного выхода значений переменных за границы диапазона. Программа, откомпилированная с активной опцией, занимает несколько больший объем памяти и исполняется медленнее, зато дает возможность контролировать выход индексов за пределы, определяемые в описании массивов.

Опция Slack checking аналогична опции Range checking и контролирует возможное переполнение программного стека.

Опция I/O checking используется для включения/отключения генерации программных кодов, контролирующих правильность операций ввода-вывода.

Установка в неактивное состояние опции Strict var -strings позволяет отказаться от проверки на совпадение длины формального и фактического параметра-строки при обращении к процедуре или функции. Если установлено активное состояние этой опции, компилятор вставляет в программу команды для сравнения длины строк.

В активном состоянии опции Complete boolean eval все логические выражения вычисляются в программе полностью, в неактивном состоянии вычисление прекращается в тот момент, когда становится ясен окончательный результат. Допустим, имеется такой фрагмент программы:

…………………………..

Funсtion MyFunc(var х: integer): Boolean

Begin

x:= x+l;

MyFunc:= x>10

End.;

…………………………..

x:= 0;

if False end MyFunc(x) then

x:= 10;

………………………….

После его компиляции с неактивной опцией Complete boolean eval исполнение этого фрагмента даст Х=0, так как не пpoизойдет обращения к функции MYFUNC: выражение FALSE AND MYFUNC всегда имеет значение FALSE вне зависимости от того, что является вторым операндом операции AND. Если же к моменту компиляции программы было установлено активное состояние этой опции, вычисление логического выражения продолжится до конца, состоится вызов функции MYFUNC и переменная Х получит значение 1. Разумеется, и в том и в другом случае не будет исполняться оператор х:= 10.

Активное состояние опции Extended syntax дает возможность использовать в программе расширенный синтаксис Турбо Паскаля, который разрешает вызывать определенные программистом функции не только в выражениях, но и в виде отдельною оператора, подобно вызовy процедуры. Отметим, что эта опция распространяется на стандартные функции.

Опция 8087/80287 ориентирует компилятор на работу с арифметическим сопроцессором. При неактивном состоянии все операции с вещественными данными реализуются программно и в программе разрешается использовать только один вещественный тип REAL. Если опция установлена в активное состояние, компилятор будет создавать код, содержащий обращения к числовому сопроцессору, причем программе становятся доступны также типы SINGLE, DOUBLE, EXTENDED и СОМР.

Опция Emulation указывает компилятору, надо ли создавать такой код программы, который будет одинаково пригоден при работе на ПК с арифметическим сопроцессором или без него. Программа сама определит наличие сопроцессора и. если он имеется, будет использовать все его возможности: если же сопроцеccopa нет, его работа будет эмулироваться программно. В атом случае программе становятся доступны все вещественные типы. Активное состояние этой опции увеличивает размеры программы за счет подключения процедур эмуляции, но делает ее независящей от аппаратных особенностей ПК. Отметим, что опция Emulution игнорируется, если неактивна опция 8087/80287.

Активное состояние опции Debug information устанавливает режим генерации отладочной информации в процессе компиляции программы. Отладочная информация представляет собой специальные таблицы, позволяющие установить однозначную связь между операторами исходного текста программы и теми кодами, которые порождает компилятор. Только после компиляции с активной опцией Debug information становится возможной автоматическая локализация ошибки периода исполнения, а также пошаговая отладка программы. Активное состояние опции увеличивает размер TPU-файлов и объем оперативной памяти, занимаемой программой, если она работает под управлением среды Турбо Паскаля, но не влияет на размер той же программы, запускаемой вне среды под управлением ДОС. Иными словами, дополнительные таблицы отладки загружаются в память только средой Турбо Паскаля, а ДОС игнорирует эту информацию.

Опция Local symbols аналогична опции Debug information и относится к именам локальных и глобальных переменных: если опция уcтановлена в активное состояние, среда поручит возможность доступа на этапе отладки к переменным по их именам.

В поле Conditional defines Вы можете задать условия, которые используются в onepaтopax условной компиляции.

MEMORY SIZES. В диалоговом окно опции OPTIONS/MEMORY SIZES используются три поля ввода. С их помощью можно регулировать размеры памяти, которую занимает программа:

Stack size - размер программного стека, по умолчанию 16384 байта, максимум - 65535 байт;

Low heap limit - минимальный размер кучи; по умолчанию 0;

High heap limit - максимальный размер кучи; по умолчанию 655360 байт; этот параметр может быть меньше параметра Low heap limit.

Для оценки необходимых программе объемов памяти следует учесть, что все локальные переменные при каждом обращении к процедуре (функции) размешаются в стеке, а при выходе из нее стек освобождается. Таким образом, требуемый размер стека определяется количеством вложенных вызовов процедур (функций) и суммарным количеством их локальных переменных. Величина кучи определяется реальными потребностями npoграммы в динамической памяти. Если установлен максимально возможный размер кучи 655360 байт, то такая программа после загрузки займет всю доступную оперативную память, а это исключит возможность запуска из нее других программ.

LINKER. В диалоговом окне этой опции имеются две группы переключаемых опций, с помощью которых регулируется режим работы компоновщика Турбо Паскаля:опции группы Map file управляют выходным документом компоновщика, опции группы Link buffer - использованием памяти. Выходной документ компоновщика (карта распределения памяти) бывает полезен при отладке программы с помощью внешнего отладчика. Опция Off запрещает формирование карты. Опция Segments формирует сегментную карту с указанием адреса запуска программы и сообщениями об ошибках периода компоновки программы. Опция Public дает такую же карту, как и опция Segment, и дополнительно приводит список внешних символов в алфавитном порядке. Наконец, опция Detailed дает полную карту распределения памяти. Опция Memory предписывает компоновщику использовать оперативную память для размещения своих таблиц и временного хранения компонуемой программы, при активной опции Disk компоновщик для этих целей использует пространство диска. Если активна опция Memory, компоновщик будет работать значительно быстрее, однако при разработке крупных программ ему может не хватить оперативной памяти и он не скомпонует программу.

Вообще, следует помнить о том, что даже довольно большой объем оперативной памяти ПК (640 Кбайт) может оказаться недостаточным для разработки с помощью среды Турбо Паскаля крупных программных проектов: ведь сам Турбо Паскаль занимает в памяти 304 Кбайт. Если обнаружена нехватка памяти, среда дает сообщение

Out of memory

(не хватает памяти)

и устанавливает курсор в конец программы. В этом случае следует прежде всего попытаться сэкономить память за счет установки в активное состояние опции Disk. Еще примерно 44 Кбайта памяти можно сэкономить за счет отказа от автоматической загрузки системной библиотеки TURBO.TPL (см. ниже опцию OPTIONS/ENVIRONMENT/STARTUP). Наконец, может оказаться необходимым отказ от услуг самой среды Турбо Паскаля на этапе прогона программы. Для этого нужно установить опцию COMPILE/DESTINATION в состояние DISK, создать программу с помощью опций MAKE или BULD, выйти из среды и запустить программу. В этом случае программа получает в свое распоряжение всю память ПК, но Вы лишаетесь возможности отлаживать се средствами встроенного отладчика. В некоторых случаях за счет оверлейной структуры программы ее размеры удается уменьшить настолько, что даже крупная программа помещается в памяти вместе со средой. Если, несмотря на все меры экономии, памяти все-таки не хватает, можно полностью отказаться от услуг среды и использовать автономный компилятор - компоновщик ТРС.ЕХЕ.

DEBUGGER. Эта опция определяет используемый отладчик и режим обновления экрана дисплея в процессе отладки. Если активна опция Integrated, к программе будет добелена информация, необходимая для работы встроенного отладчика. Только в этом состоянии опции можно использовать контрольные точки и пошаговую отладку. При активизации опции Standalone к EXE - файлу программы будут добавлены соответствующие таблицы, которые позволят вести отладку программы вне среды Турбо Паскаля с помощью внешнего отладчика TD.EXE. Три других опции сообщают среде, в каких случаях следует переключать экран с воспроизведения окна редактора на окно программы. В режиме Smart среда будет переключать экран по мере надобности - только если в очередном операторе программы было обращение к экрану для вывода или к клавиатуре для ввода. Переключение на окно программы будет также и тогда, когда отладчик «перескакивает» через вызов процедуры (функции) по клавише F8, но в этой процедуре (функции) есть обращение к экрану. Если установлен режим Always, переключение будет происходить перед исполнением любого оператора программы. Наконец, в режиме None среда никогда не переключает экран, даже если он требуется для вывода данных, т.е. вывод программы будет накладываться на текст программы. Испорченный в результате такого прогона текст в окне редактора можно обновить с помощью опции Window/Refresh display.

DIRECTORIES. Четыре поля ввода в диалоговом окне опции OPTIONS /DIRECTORIES позволяют определить четыре группы функциональных каталогов Турбо Паскаля.

ЕХЕ & TPU directories указывает тот каталог, в который будут помещаться готовые к работе программы в виде EXE -файлов и результат компиляции модулей в виде TPU -файлов. Если каталог не указан, эти файлы будут помещаться в текущий каталог - именно такое состояние этой опции соответствует стандартной настройке среды. Не рекомендуется устанавливать в этой опции каталог, содержащий файлы системы Турбо Паскаль.

Include directories - здесь следует перечислить те каталоги, в которых Турбо Паскаль будет искать включаемые файлы, т.е. файлы, задаваемые директивой компилятору {$I<имя файла>}. При указании нескольких каталогов, они перечисляются через точку с запятой. Отметим, что поиск в этих каталогах идет только в том случае, если включаемый файл не найден в текущем каталоге.

Unit directories - задает каталоги, в которых среда ищет TPU -файлы, если они не обнаружены в текущем каталоге. В этой опции обычно указывается каталог, содержащий файл GRAPH.TPU (если в npoграмме используются графические средства Typбо Паскаля), а также каталог, указанный в поле ЕХЕ & TPU directories. При перечислении нескольких каталогов они разделяются точкой с запетой.

Если в своей программе Вы используете внешние процедуры и функции они должны быть представлены в виде OBJ -файлов. Поле Object directories задает один или несколько каталогов, в которых Турбо Паcкаль будет искать эти файлы, если их нет в текущем каталоге.

Изучение методов сортировки

Сортировка – операция, упорядочивающая последовательность (массив) элементов по ключам. Ключ – некоторое числовое свойство элемента массива, т.е. каждому элементу массива ставиться в соответствие некоторое число, которое называется ключом элемента.

Если мы имеем числовой массив, то ключ элемента – это сам элемент. В этом случае сортировка массива – это упорядочивание массива (перестановка его элементов) таким образом, чтобы получилась неубывающая или невозрастающая последовательность.

Если каждый элемент исходного массива представляет собой слово, составленное из букв русского алфавита, то ключ, по которому может быть упорядочен массив, связывается с порядковым номером буквы в алфавите. По этому принципу упорядочиваются слова в словарях – раньше помещается то слово, ключ которого меньше. Здесь принимается, что отсутствие буквы (“пустая” буква) имеет меньший ключ, чем любая другая буква. Так слово “студент” помещается в словаре перед словом “студентка”.

Если слова состоят из букв и цифр, как, например, имена файлов, то считается, что любая цифра имеет меньший ключ, чем любая буква. Как мы знаем, каждому символу, изображенному на клавиатуре компьютера, соответствует код в некоторой кодовой таблице. Этот код и есть ключ, по которому происходит упорядочивание имен. Так имена:

h10ga, g2, g10, ha10g

будут упорядочиваться в соответствии с возрастанием кодов символов

следующим образом:

g10, g2, h10ga, ha10g.

Указанный выше принцип упорядочивания слов называется лексикографическим порядком.

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

Ясно, что с отсортированными данными работать легче, чем с произвольно расположенными. Когда элементы отсортированы, их проще найти и установить, что их нет. Представьте себе, что в толковом словаре слова будут расположены в том порядке, в каком составители получали их объяснения от специалистов. Как вы будете искать нужное вам слово?

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

Ниже рассматриваются алгоритмы сортировки числовых массивов, но все сказанное справедливо и для произвольных массивов записей.

Заметим ещё в заключении, что, когда говорят возрастание (убывание), то предполагают, что в массиве одинаковых элементов нет. В общем случае надо вместо “возрастания” говорить “неубывание”, а вместо “убывание” – “невозрастание”.

При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.

Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:

· количество присваиваний;

Или

· количество сравнений.

Мы за скорость будем принимать отношение количества сравнений к общему числу элементов.

Все методы сортировки можно разделить на две большие группы:

· простые (прямые) методы сортировки;

· улучшенные методы сортировки.

Простые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на четыре подгруппы:

· сортировка обменом (“пузырьковая” сортировка);

· сортировка выбором (выделением или извлечением);

· сортировка вставкой (включение);

· сортировка методом попарного сравнения).

Улучшенные методы сортировки основываются на тех же принципах, что и простые, но используют некоторые оригинальные идеи для ускорения процесса сортировки. Простые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из простых методов сортировки могут даже превзойти улучшенные методы.

1.3. Классификация методов сортировки