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

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

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

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

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

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

Исполнитель

студент группы 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 примерно оценивается формулой:

--> ЧИТАТЬ ПОЛНОСТЬЮ <--