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

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И  НАУКИ УКРАИНЫ

ХЕРСОНСКИЙ  ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

рАЗРАБОТКА ПРОГРАММЫ ДЛЯ

Анализа методов сортировки одномерных массивов.

Курсовой  проект

по  дисциплине «Программирование»

Пояснительная записка

Исполнитель

студент группы 2КСС3 ________________________

(подпись, дата)

Руководитель

старший преподаватель ________________________

(подпись, дата)

Нормоконтролер

старший преподаватель_________________________

(подпись, дата)

РЕФЕРАТ

Курсовой  проект содержит: стр. - 39 машинописного текста, литературных источников - 5, приложения - 2 .

Ключевые слова: ФУНКЦИЯ, ФАЙЛ, МЕТОД , МАССИВ .

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

 

СОДЕРЖАНИЕ

Введение 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 - неизвестные константы, зависящие от программной реализации алгоритма.

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

Идея алгоритма  состоит в обмене элементов, расположенных  не только рядом, как в алгоритме  простых вставок (п.1), но и далеко друг от друга, что значительно сокращает  общее число операций перемещения  элементов. Для примера возьмем  файл из 16 элементов. Сначала просматриваются  пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены  по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап - 4-сортировка, на котором  элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15,4-8-12-16. Выполняется  сортировка в каждой четверке. Сортировка может выполняться методом простых  вставок (п.1). Следующий этап - 2-сортировка, когда элементы в файле делятся  на 2 группы по 8:

1-3-5-7-9-11-13-15 и  2-4-6-8-10-12-14-16. Выполняется сортировка  в каждой восьмерке. Наконец  весь файл упорядочивается методом  простых вставок. Поскольку дальние  элементы уже переместились на  свое место или находятся вблизи  от него, этот этап будет значительно  менее трудоемким, чем при сор-тировке вставками без предварительных "дальних" обменов.

Файл после  окончательной сортировки (1-сортировки): 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908

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

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

ции алгоритма.

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

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

- просмотра исходного  файла со сравнением переменной  Х с

элементами K[i] файла;

- вставки нового  элемента путем сдвига оставшихся  элементов

вправо.

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

Дан файл в виде связанныого списка, каждый элемент которого содержит кроме ключа K[i] еще и указатель на следующий элемент L[i].

Кроме того есть еще дополнительная переменная L[0], содержащая указатель на последний N-й элемент файла. Указатель L[N] равен  нулю, что является признаком конца  списка элементов.

Время работы алгоритма t примерно оценивается формулой: t=a*NЅ + b*N

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