Добавить в корзину Удалить из корзины Купить |
Классы алгоритмов сортировки ID работы - 747896 информатика (реферат) количество страниц - 21 год сдачи - 2008 СОДЕРЖАНИЕ: Содержание Введение 3 1. Классы алгоритмов сортировки 4 2. Оценка алгоритмов сортировки 5 3. Сортировка выбором 7 4. Пирамидальная сортировка 9 Заключение. 16 Список использованной литературы 17 Приложение 1. Листинг процедуры сортировки выбором 18 Приложение 2. Листинг пирамидальной сортировки 19 ВВЕДЕНИЕ: Введение В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<="). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа. Различают сортировку массивов записей, целиком расположенных в основной памяти (внутреннюю сортировку), и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти (внешнюю сортировку). Для внутренней и внешней сортировки требуются существенно разные методы. Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M). Заметим, что поскольку сортировка основана только на значениях ключа и никак не затрагивает оставшиеся поля записей, можно говорить о сортировке массивов ключей. В следующих разделах, чтобы не привязываться к конкретному языку программирования и его синтаксическим особенностям, мы будем описывать алгоритмы словами и иллюстрировать их на простых примерах. 1. Классы алгоритмов сортировки Имеется три способа сортировки массивов: " сортировка обменом; " сортировка выбором; " сортировка вставкой. Представьте, что перед вами лежит колода карт. Для сортировки карт обменом вы должны разложить карты на столе лицевой стороной вверх и затем менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной. Для сортировки выбором вы должны разложить карты на столе, выбрать самую младшую карту и взять ее в свою руку. Затем вы должны из оставшихся на столе карт вновь выбрать наименьшую по значению карту и поместить ее позади той карты, которая уже имеется у вас в руке. Этот процесс вы должны продолжать до тех пор, пока все карты не окажутся у вас в руках. Поскольку каждый раз вы выбираете наименьшую по значению карту из оставшихся на столе, по завершению такого процесса карты у вас в руке будут отсортированы. Для сортировки вставкой вы должны держать карты в своей руке, поочередно снимая карту с колоды. Каждая взятая вами карта помещается в новую колоду на столе, причем она ставится на соответствующее место. Колода будет отсортирована, когда у вас в руке не окажется ни одной карты. 2. Оценка алгоритмов сортировки Для каждого метода сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки зависит от ответов, которые будут получены на следующие вопросы: " с какой средней скоростью этот алгоритм сортирует информацию?; " какова скорость для лучшего случая и для худшего случая?; " поведение алгоритма является естественным или является не естественным?; " выполняется ли перестановка элементов для одинаковых ключей? Для конкретного алгоритма большое значение имеет скорость сортировки. Скорость, с которой массив может быть упорядочен, прямо зависит от числа сравнений и числа необходимых операций обмена, причем операции обмена занимают большое время. Время работы алгоритма для лучшего и худшего случаев важно учитывать, когда ожидается их частое появление. Часто сортировка имеет хорошую среднюю скорость, но очень плохую скорость для худшего случая, и наоборот. Считается поведение алгоритма сортировки естественным, если время сортировки наименьшее при упорядоченном списке элементов, время сортировки увеличивается при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке. Время сортировки зависит от числа операций сравнения и операций обмена. Для того, чтобы понять важность перегруппировки элементов с одинаковыми ключами сортировки, представим базу данных, которая упорядочена по основному ключу и дополнительному ключу. /Например, список почтовых отправлений с почтовым индексом в качестве основного ключа и фамилией в качестве дополнительного ключа в рамках одного почтового индекса/. Когда новый адрес добавляется в список и список вновь сортируется, вам не требуется перестановка дополнительных ключей. Для обеспечения этого сортировка не должна выполнять операции обмена для основных ключей с одинаковыми значениями. Каждая программа сортировки использует два типа данных, определенных пользователем, которые определяются следующим образом: type DataItem = char; DataArray = array [1..80] of DataItem; Следовательно, для изменения используемых в сортировках типов данных требуется изменить только эти два определения типов. Размерность массива выбрана произвольно и вы можете при необходимости их изменить. СПИСОК ЛИТЕРТУРЫ: Заключение. В данной курсовой работе я дал определение понятия сортировка, провел обзор основных методов сортировки, подробно рассмотрел сортировку простым выбором и пирамилальную сортировку. В приложениях 1 и 2 приведены листинги программ, в которых реализованы эти два вида сортировок. Цена: 750.00руб. |
ЗАДАТЬ ВОПРОС
Copyright © 2009, Diplomnaja.ru