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

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

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

 

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

 

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

 

 

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

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

 

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

 

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

 

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

 

Исполнитель

студент группы 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 элементов.

Страницы: 1, 2, 3, 4, 5



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.