Файл: Алгоритмы сортировки данных (Выбор языка программирования).pdf

ВВЕДЕНИЕ

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

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

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

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

Объектом исследования являются алгоритмы сортировки данных.

Предмет исследования - методы использования алгоритмов сортировки и их применение при реализации на языках программирования высокого уровня.

В процессе выполнения курсовой работы будут решены следующие задачи:

1. Провести анализ предметной области.

2. Рассмотреть и провести анализ основных алгоритмов сортировки данных.

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

4. Запрограммировать выделенные алгоритмы сортировки.

5. Провести тестовые запуски алгоритмов и снятие показателей (количество операций перестановки и времени работы алгоритмов).

6. Разработать руководство пользователя для работы с программой.

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).

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

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

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