Файл: Алгоритмы сортировки электронных данных.pdf

ВВЕДЕНИЕ

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

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

Алгоритмы информационного поиска и сортировки очень тесно связаны друг с другом. Они образовали фактически отдельный класс алгоритмов. Этот класс интересен и с точки зрения обучения, и с точки зрения использования при решении многих задач. Специфической особенностью данного класса является то, что внешне тривиальные задачи: «найти элемент» или «упорядочить последовательность элементов» допускают разнообразные решения.

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

Объектом исследования является алгоритмизация.

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

Для достижения поставленной цели нужно решить следующие задачи:

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

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

Теоретическое значение курсовой работы заключается в приобретении опыта обработки, анализа и систематизации результатов практических (экспериментальных) исследований.

Курсовая работа состоит из введения, четырех разделов, списка используемой литературы. Работа содержит 3 рисунка и 5 таблиц.

1. Основы алгоритмизации

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

Первый этап развития методов сортировки данных начался в 1870 году и длился до начала 1940-х годов. Его ознаменовал переход от ручной сортировки к сортировке с помощью статистических табуляторов. При этом использовался алгоритм поразрядной сортировки.

Второй этап — с начала 1940-х годов до середины 1950-х. На смену счетно-перфорационным машинам пришли ЭВМ первого поколения, для которых был разработан ряд новых алгоритмов сортировки. Произошло их разделение на внутренние и внешние.

Третий этап начался в середине 1950-х годов и продолжался до середины 1970-х. Для него было характерно активное развитие алгоритмов сортировки — внешней и внутренней, устойчивой и неустойчивой — многие, из которых широко используются и в настоящее время. Наибольшее количество разработанных к тому времени методов относилось к сортировке путем вставок, обменной сортировке и сортировке посредством выбора.

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

Пятый этап начался с середины 1990-х годов и продолжается по настоящее время. Особую актуальность получило исследование задач сортировки на частично упорядоченных множествах: задач распознавания частично упорядоченного множества М; задач сортировки частично упорядоченного множества М с использованием результатов попарных сравнений элементов, а также задач определения порядка на множестве М без априорной информации. Актуальность задач сортировки объясняется появлением и широким распространением компьютеров на сверхсложных микропроцессорах с параллельно-векторной структурой, а также высокоэффективных сетевых компьютерных систем.

Важное практическое значение проблема сортировки данных в больших массивах впервые приобрела в США в середине XIX века. В 1840 году там был создан центральный офис переписи населения, куда стекались первичные данные из всех штатов. В ходе переписи было опрошено 17 069 453 человек, каждая анкета состояла из 13 вопросов. Объем полученных данных был столь велик, что их обработка традиционным ручным способом потребовала непомерных затрат труда и времени.^[1]

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

Конкурс выиграл американский инженер и изобретатель Герман Холлерит.

Вот как были описаны преимущества машины Холлерита в русском журнале «Вестник Опытной Физики и Элементарной Математики» в 1895 году: «Преимущества машины Холлерита заключаются: в значительном ускорении и удешевлении работы. При ручном способе можно разложить и подсчитать за час не более 400 карточек. Если принять, что в Российской Империи 120 миллионов жителей, то для изготовления одной только сводной таблицы потребуется не менее … 300 000 часов… Машина сокращает работу почти в 5 раз. После немногих пропусках через машину всех счетных карточек получаются столь полные и разнообразные таблицы, составление которых было почти немыслимо при прежнем способе».

Следующий этап развития способов и алгоритмов сортировки начался в начале 1940-х годов с появлением первых электронных вычислительных машин. Фантастическое по тем временам быстродействие ЭВМ вызвало рост интереса к новым, приспособленным для машинной обработки алгоритмам сортировки. В 1946 году вышла первая статья об алгоритмах сортировки данных, автором которой был Джон Уильям Мочли — американский физик и инженер.

В середине 1950-х годов с разработкой ЭВМ второго поколения началось активное развитие алгоритмов сортировки. Основными предпосылками для этого стали, во-первых, значительное упрощение и ускорение написания программ для компьютеров в результате разработки первых языков программирования высокого уровня (Фортран, Алгол, Кобол); во-вторых, значительное повышение доступности компьютеров в результате резкого уменьшения их габаритов и стоимости и, как следствие, достаточно широкое их распространение; в-третьих, увеличение производительности компьютеров до 30 тысяч операций в секунду.^[2]

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

В период с середины 1970-х до 1990-х годов были достигнуты значительные успехи в увеличении скорости сортировки за счет повышения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. К примеру, нидерландский учёный Эдсгер Вибе Дейкстра в 1981 году предложил алгоритм плавной сортировки (Smoothsort), который является развитием пирамидальной сортировки (Heapsort).

1.2. Понятие алгоритма и сортировки

Алгоритм сортировки — это алгоритм для упорядочивания элементов. Прежде чем переходить к рассмотрению конкретных методов сортировки и алгоритмов поиска, необходимо определить понятия алгоритмизация и алгоритм. Из истории известно, что самый первый алгоритм принадлежит древнегреческому математику Евклиду. Ему принадлежит правило нахождения максимального общего делителя двух целых чисел. В математике понятие алгоритма является основным понятием, восходящее к работам выдающегося узбекского математика IX века Аль-Хорезми. В 12 веке его работы по арифметике и алгебре были переведены на латынь. Данные работы заложили основу всей европейской математики.

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

Исчерпывающее определение алгоритма дал выдающийся отечественный математик А.А. Марков. Алгоритм – это точное предписание, которое определяет процесс преобразования исходных данных в необходимый результат. Алгоритм должен обладать следующими свойствами:^[3]

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

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

Чтобы алгоритм был работоспособный, необходимо чтобы каждая из таких инструкций могла удовлетворять условиям массовости и точности.^[4]

Обеспечить массовость (выполнимость) алгоритма значит исключить из него все невыполнимые команды. Обеспечить точность означает исключить бессмысленные и неясные инструкции.

Другими словами, для точности (определенности) алгоритма каждая из частей его инструкций должна быть определена недвусмысленно и четко. Если алгоритм выражен на естественном языке, то здесь есть возможность появления неоднозначности. Д. Кнут. предложил неформальное определение термина выполнимость. Согласно Кнуту, инструкция выполнима, если включенные в нее инструкции достаточно элементарны, чтобы они за конечное время могли быть выполнены человеком, вооруженным карандашом и бумагой. То, что даже простая инструкция может оказаться невыполнимой демонстрирует следующий простой. Например, вычислить наибольшее вещественное число, меньшее единицы. С точки зрения математики такое число определить невозможно – например, если выбрать число 0.999999999, число 0.9999999991 будет больше.

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

Шаг 1: Присвоить S значение 0.

Шаг 2: Присвоить S значение S+5.

Шаг 3: Перейти к шагу 2.

Для каждого алгоритма важно, чтобы была доказана его конечность.

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

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