Файл: Алгоритмы сортировки данных. (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ АЛГОРИТМА СОРТИРОВКИ ДАННЫХ).pdf

ВВЕДЕНИЕ

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

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

Научное значение данная работа представляется в анализе и представлении самых известных алгоритмов сортировки. Практическое значение тема «Алгоритмы поиска и сортировки» представляется в исследовании проблем выполнения и применения разных типов алгоритмов поиска и сортировок.

Цель работы – алгоритмы сортировки данных.

Объектом исследования - алгоритмы сортировки данных с использованием технологии MPI.

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

Сразу надо отметить, вопросами анализа алгоритмов, группировкой, исследованием и методами их программирования в различные времена были заняты: Кнут Д., Ульман Дж., Левитин А., Цейтлин Г.Е., Гудман С., Хидетниеми С., Ахо А., Хлопккрофт Дж., Вирт Н., Лорин Г., Макконнелл Дж. и другие.

ГЛАВА 1 ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ АЛГОРИТМА СОРТИРОВКИ ДАННЫХ

1.1 Алгоритм сортировки данных

Алгоритм (algorithm) — это любой корректно определенный вычислительный процесс, на входе (input), которого задается какое-то значение или набор значений, а итогом реализации является выходное (output) значение или набор величин. Значит, алгоритм это определенная последовательность вычислительных шагов, которые преобразуют входные значения в выходные.

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

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

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

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

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

Основные критерии эффективности алгоритмов сортировки следующие:

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

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

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

Во многих программах сортировки оптимально применить простые элементарные алгоритмы. Программы сортировки иногда применяются только единожды (или несколько раз). В случае, когда количество элементов, необходимых отсортировать небольшое (примерно меньше 500 элементов), то тогда применение элементарного алгоритма даст больший эффект, чем новая проработка и отладка громоздкого алгоритма. Элементарные простые методы постоянно полезны для небольших файлов (примерно меньших, чем 50 элементов); конечно сложный алгоритм было бы неразумно применить для подобных файлов, если конечно нет необходимости отсортировать большое количество подобных файлов.

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

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

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

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

Объем применяемой дополнительной памяти алгоритма сортировки – также дополнительный фактор, принимаемый во внимание. Обычно методы сортировки делят на три группы:

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

Стабильность – также важная свойство методов сортировки. Метод сортировки является стабильным в случае, когда он сохраняет относительный порядок расположения записей с одинаковыми ключами. К примеру, когда алфавитный список учащихся ранжируется по оценкам, тогда стабильный метод организует список, где фамилии учащихся с одинаковыми баллами будут отсортированы по алфавиту, а нестабильный метод организует список, где, возможно, начальный порядок будет нарушен. Большая часть простых методов стабильны, тогда как большая часть всем известных сложных методов – нет. В случае, когда стабильность необходима, тогда можно её добиться путем добавления к ключу маленького индекса перед процессом сортировки или посредством удлинения, каким-то путем, ключа. Стабильность легко принимают за норму; к нестабильности у людей отношение с недоверием. Фактически, только некоторые методы добиваются стабильности без применения дополнительного времени или места.

Для выявления эффективности алгоритма необходимо оценить числа С – нужных сравнений ключей и М – присваиваний элементов. Указанные числа рассчитываются определенными формулами от числа n сортируемых элементов. Удовлетворительные алгоритмы сортировки используют примерно сравнений.

Условимся по терминологии: мы имеем элементы – a₁, a₂, …, a_n. Процедура сортировки предполагает такую перестановку данных элементов в следующем порядке: a_k1, a_k2, …, a_kn, что при данной функции упорядочения f верно отношение f(a_k1)<=f(a_k2)<=…<=f(a_kn).

Чаще всего функция упорядочения не определяется по определенному правилу, а входит в каждый элемент в виде явной компоненты (поля). Значение этой компоненты является ключом элемента. Для выражения элемента a_i используется следующее выражение:

type item = record

key: integer;

{описание прочих элементов}

end;

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

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

1.2 Программный и аппаратный алгоритм сортировки данных

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

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

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