Файл: Сортировка слиянием.pdf

ВВЕДЕНИЕ

Данная курсовая работа по предмету «Основы алгоритмизации и программирования» посвящена методам сортировки данных: их эволюции и сравнительному анализу, а также примерам использования. Прежде чем приступить к исследованию методов сортировки данных, необходимо отметить, что такое сортировка. Сортировка - это процесс упорядочивания наборов данных одного типа по возрастанию или убыванию значения какого-либо признака. Существует довольно много различных методов сортировки, отличающихся друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки, время выполнения и объем занимаемой операционный памяти. Значимость темы «методов сортировки данных» основана на том, что массивы информации могут быт быстро и точно обработаны только тогда, когда информация однородна и отсортирована.

Объектом исследования курсовой работы являются массивы данных, предметом – алгоритмы сортировки. Целью курсовой работы является исследование исторического аспекта методов сортировки данных, описание различных методов сортировки данных и их сравнительный анализ.

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

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

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

Основным источниками для ссылок к курсовой работе является 3-й том многотомной монографии американского ученого, преподавателя программирования Дональда Эрвина Кнута, посвященный вопросам сортировки и поиска, и книга «Фундаментальные алгоритмы на С++» другого американского ученого в области информатики Роберта Седжвика (защита диссертации про алгоритм быстрой сортировки под руководством Д.Кнута). Множество деталей, касающихся математического анализа и практических эффектов многих модификаций и усовершенствований, появившихся после широкого распространения алгоритма быстрой сортировки, можно найти в статье Седжвика за 1978 г.

Следует сказать, что вопросами исследования алгоритмов, их классификацией, анализом и способами их программирования в разное время занимались такие ученые как: Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д., Макконнелл Дж. Также при написании курсовой работы были использованы материалы, полученные от отечественных авторов – профессор МЭИ Зубов В.С., Полунов Ю. Исторический аспект методов эволюции изучался у таких авторов как Гук М.Ю., Заславская О.Ю., Кравец О.Я., Частиков А.

1. Эволюция методов сортировки данных

1.1. Понятие сортировки

Сортировка является одной из фундаментальных алгоритмических задач программирования. Решению проблем, связанных с сортировкой, посвящено множество научных исследований, разработано множество алгоритмов [10, С. 249].

В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.

Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию [10, С. 250].

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

В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки. Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными [10, С. 250].

Практически каждый алгоритм сортировки можно разбить на 3 части:

1. сравнение, определяющее упорядоченность пары элементов;
2. перестановку, меняющую местами пару элементов;
3. собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

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

Ни одна другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Универсального, наилучшего алгоритма сортировки на данный момент не существует. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом. Для этого необходимо знать параметры, по которым будет производиться оценка алгоритмов [7, С. 99].

Время сортировки – основной параметр, характеризующий быстродействие алгоритма.

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

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

Естественность поведения – параметр, которой указывает на эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше [6, С. 103].

1.2. Методы сортировки в XIX веке

Первые прототипы современных методов сортировки появились уже в XIX веке.

В конце XIX в. перепись населения как одна из важнейших статистических задач проводилась регулярно - через 10 лет, это требование статистики строго соблюдали все развитые страны. Обработка полученных данных проводилась в течение нескольких лет, как правило, вручную или с помощью механических вычислительных машин [3, С. 105].

Впервые проблемой механизированной обработки статистической информации занялся талантливый американский изобретатель Герман Холлерит. Его трудовая деятельность началась в Бюро цензов США. Это статистическое управление при министерстве внутренних дел занималось проведением переписей населения и обработкой результатов. Здесь в 1880 г. Холлерит познакомился с доктором Джоном Биллингсом, который сыграл важную роль в его дальнейшей судьбе, предложив заняться исследованиями в области механизированной обработки статистических данных и использовать в качестве основного элемента записи информации, получаемой в процессе переписей и ее последующей обработки, перфорированные карты [1, С. 503].

Г. Холлерит долго придерживался другой точки зрения, он был уверен, что наиболее эффективно использовать для записей статистических данных перфоленты и придумал конструкцию специального барабана, на который наматывалась перфолента, и счетчиками отсчитывались отверстия. И все-таки изобретатель был вынужден признать свою идею несостоятельной, т. к. перфолента не способствовала оперативной работе с той или иной записью на длинной бумажной ленте. Он вернулся к предложению Дж. Биллингса и разработал специальную перфокарту, куда в виде пробивок наносились все данные об одном человеке.

Идея перфокарт уже была известна в мире и нашла практическое применение в ткацких станках Ж. Жаккара (1804) и вычислительной машине Ч. Бэббиджа (1833). Не исключено, что Г. Холлерит знал об этом, но как он сам вспоминал, к этой идее его подтолкнула работа кондуктора. Оказывается, в США, чтобы предотвратить мошенничество на железных дорогах и кражу билетов, кондукторы "записывали" физические особенности пассажиров (цвет волос, глаз и т. п.) компостером в специально отведенных местах на билете [6, С. 430].

Замысел Г. Холлерита состоял в том, чтобы на каждого человека завести личную карточку и все подлежащие обработке данные представить отверстиями в фиксированных местах (позициях). Эта перфокарта по виду была не похожа на железнодорожный билет или уже известные карты, а являлась оригинальной авторской запатентованной разработкой. Она была сделана из плотного картона размером приблизительно с долларовую бумажку, но размер карточки мог колебаться в зависимости от количества позиций, каждая из которых отвечала за определенный признак (пол, семейное положение, вероисповедание и т. д.), например, в австрийской переписи 1890 г. применялись перфокарты, имеющие 20х12 позиций, в российской переписи 1897 г. - 22х12 позиций [6, С. 431].

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

Теперь можно было либо подсчитать отверстия на всех перфокартах на основной машине - табуляторе, либо распределить их по тому же принципу на сортировке [6, С. 432].

1.3. Развитие в первой половине ХХ века

Дальнейшее развитие алгоритмов связано с развитием электронно-вычислительных машин, поэтому следующим этапом в эволюции сортировки данных можно считать компьютер EDVAC и программу сортировки для нее, написанную Джоном фон Нейманом (28 декабря 1903 — 8 февраля 1957). Ряд исследователей считают фон Неймана одним из основателей вычислительной техники. Дональд Кнут называет фон Неймана изобретателем, который в 1945 году разработал алгоритм сортировки слиянием, в котором первая и вторая половины массива сортируются рекуррентно, а потом сливаются [6, С. 418].

При создании EDVAC рассматривались различные варианты построения ЭВМ, в том числе вариант, предусматривающий использование ртутных ультразвуковых линий задержки (РУЛЗ) в качестве оперативной памяти в машине, которую авторы назвали “Электронной вычислительной машиной с переменной дискретностью” (Electronic Discrete Variable Computer, EDVAC) [6, С. 419].

Вычислительную машину фон Нейман определял как “устройство [device], которое может выполнять команды для вычислений значительной сложности” [9, С. 8]. Он отмечал, что команды, управляющие выполнением вычислительных и других операций, необходимо сообщать устройству с максимально допустимой детализацией; устройство должно иметь возможность их воспринимать и все команды полностью выполнять без какого-либо вмешательства человека. Последнее требуется лишь при обнаружении и исправлении допущенных при вычислениях ошибок, неизбежных в процессе функционирования устройства (ввиду его сложности и большого числа выполняемых операций). Впрочем, такое вмешательство можно сократить до минимума, поскольку устройство может самостоятельно определять часто повторяющиеся ошибки и либо автоматически корректировать их и продолжать вычисления, либо прекращать процесс [9, С. 8].

Фон Нейман планировал EDVAC как синхронную ЭВМ с АУ последовательного действия, выполняющим операции над числами с фиксированной запятой. Длина адресного поля составляла 13 двоичных разрядов (восемь разрядов определяли номер РУЛЗ, остальные пять — адрес машинного слова); для данных было отведено 30 разрядов (плюс знаковый разряд), отрицательные числа представлялись в форме двоичного дополнения. Еще один разряд был отведен под признак (tag): наличие в нем нуля означало, что машинное слово представляет собой число. В качестве памяти использовались 256 РУЛЗ, работавших на тактовой частоте 1,0 МГц. Каждая из них могла хранить 32 тридцатидвухразрядных слова, таким образом, емкость памяти составляла 8К слов [6, С. 418]. АУ содержало три неадресуемых регистра, организованных наподобие стека: данные всегда вводились в первый (верхний) регистр, при этом его содержимое выталкивалось во второй регистр; третий регистр был аккумулятором: он выполнял операции над операндами, находившимися в первых двух регистрах, и сохранял результат, который мог быть направлен из него в другие блоки. У команд EDVAC была сложная иерархическая структура, состоявшая из восьми базовых кодов (basic codes), десяти дополнительных кодов (sub-codes) и одного модификатора (modifier). Машина имела последовательное, или, как иногда говорят, естественное управление операциями: в начале работы в командный регистр вводился адрес первой команды, она извлекалась из памяти, декодировалась и выполнялась, после чего содержимое программного счетчика увеличивалось на единицу, из памяти извлекалась следующая команда, и машинный цикл повторялся (если в разряде признака очередного машинного слова находился нуль, оно загружалось в верхний регистр АУ). Исключение составляли команды безусловной и условной передачи управления (выполнение последней зависело от знака числа в аккумуляторе). По оценкам фон Неймана, EDVAC должна была содержать примерно 2000—3000 электронных ламп [6, С. 420].