Анализ методов сортировки одномерного массива

СОДЕРЖАНИЕ

Введение 3

1. Постановка задачи . 5

1.1. Анализ существующих решений поставленной задачи . 5

1.2. Обоснование выбора метода решения задачи 16

2. Разработка алгоритма решения задачи . 17

3. Разработка программы 18

3.1 Описание программы и используемых в ней функций . 18

3.1.1 Описание функции main() . 21

3

.1.2 Описание функции srecmg() . 21

3.1.3 Описание функций qqsort() 22

3.1.4 Описание функции grafix() . 23

3.2 Руководство программиста . 25

3.3 Руководство оператора . 26

Заключение . 28

Список использованной литературы . 29

Приложение 1 30

Приложение 2 39

ВВЕДЕНИЕ

Си – это язык программирования общего назначения, хорошо известный своей эффективностью, экономичностью, и переносимостью. Указанные преимущества Си обеспечивают хорошее качество разработки почти любого вида программного продукта. Использование Си в качестве инструментального языка позволяет получать достаточно быстрые и компактные программы. Во многих случаях программы, написанные на Си, сравнимы по скорости с программами, написанными на языке ассемблера[2]. При этом они имеют лучшую наглядность.

Си сочетает эффективность и мощность в относительно малом по размеру языке. Хотя Си не содержит встроенных компонент языка, выполняющих ввод-вывод, распределение памяти, манипуляций с экраном или управление процессами, тем не менее, системное окружение Си располагает библиотекой объектных модулей[3], в которой реализованы подобные функции. Библиотека[4] поддерживает многие из функций, которые требуются.[1]

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

Он тесно связан с операционной системой "UNIX"[4] , так как был развит на этой системе и так как "UNIX" и ее программное обеспечение написано на "C". Сам язык, однако, не связан с какой–либо одной операционной системой или машиной; и хотя его называют языком системного программирования, так как он удобен для написания операционных систем, он с равным успехом использовался при написании больших вычислительных программ, программ для обработки текстов и баз данных [2].

2. ПОСТАНОВКА ЗАДАЧИ

2.1 АНАЛИЗ СУЩЕСТВУЮЩИХ РЕШЕНИЙ ПОСТАВЛЕННОЙ ЗАДАЧИ

В настоящее время существует множество алгоритмов cортировки[5] массивов, которые применяются в зависимости от того какие условия функционирования стоят перед разрабатымаемой программой.

1. Методы вставки. Алгоритм простых вставок.

1.1. Бинарные вставки

1.2. Двухпутевые вставки

1.3. Вставки одновременно нескольких элементов.

1.4. Вставки с убывающим шагом (метод Шелла)

1.5. Вставки в связанный список

1.6. Вставки в несколько связанных списков

2. Обменная сортировка

2.1. Метод пузырька

2.2. Модификация метода пузырька

2.3. Быстрая сортировка.

2.4. Обменная поразрядная сортировка

2.5. Параллельная сортировка Бэтчера

3. Сортировка посредством выбора

( Использование связанного списка для хранения

информации о промежуточных максимумах.)

4. Сортировка посредством слияния

Методы вставки. Алгоритм простых вставок.

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

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

Время работы алгоритма t примерно оценивается формулой:

t=a*NЅ+ b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Бинарные вставки

Для ускорения числа сравнений при поиске места, в которое нужно вставить элемент X, можно использовать логарифмический [5] поиск. Это означает, что сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2+1 и j и т.д. . При этом числосравнений для каждого j равно примерно log(j). Число пересылок эле ментов при этом не изменяется и остается примерно равным NЅ/4.

Время работы алгоритма t примерно оценивается формулой:

t=a*NЅ + b*N + c*N*logN

где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма.

Двухпутевые вставки

Число пересылок можно сократить примерно в 2 раза до NЅ/8, если допустить сдвиги элементов не только вправо, но и влево. Для выходного файла резервируется место в памяти, равное 2N+1 ,где N - число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов. Присоединение новых элементов к выходному файлу происходит как справа, так и слева от центрального элемента с возможным сдвигом вправо или влево.

Время работы алгоритма t примерно оценивается формулой:

t=a*NЅ + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Вставки одновременно нескольких элементов.

Модификация метода простых вставок заключается в том, что вместо одной переменной Х можно использовать несколько переменных Х1, Х2, . Xm, которые имеют значения элементов, подлежащих вставке в уже упорядоченную часть файла. Х1, X2, . Xm упорядочены по возрастанию, поэтому сравнивая Xm в цикле по переменной i с элементами упорядоченной части, мы можем гарантировать, что, если очередной элемент k[i] больше Xm, то он больше и остальных элементов. Перенос элементов исходного файла вперед в цикле по i выполняется на m элементов, то есть вместо k[i+1]=k[i] в исходном алгоритме в модифицированном алгоритме записывается k[i+m]=k[i]. При нахождении k[i] такого, что он меньше Хm, Хm ставится на место k[i+m] и m уменьшается на 1. Далее цикл по i продол-жается с новым m. Экономия числа переносов элементов достигается за счет переносов сразу на m элементов.

Время работы алгоритма t примерно оценивается формулой:

t=a*NЅ + b*N + c*N*logN

где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма.

 Скачать реферат