Сортировка матриц

Министерство образования и науки Российской Федерации

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

 

Факультет информационных технологий

 

Кафедра вычислительной техники

КУРСОВАЯ  РАБОТА

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

 

Сортировка матриц

 

ОГУ 230100.62.1107.006.О

 

 

 

 

 

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

                                                                               Медведев В. А.

                                                                               ________________

                                                                               "___"_____________2012 г.

                                                                               Выполнил:

                                                                               Студент группы11ИВТ(б)ВМК

                                                                               Кожевников Н.В.        

                                                                                _________________   

                                                                               "___"_____________2012 г.

    

 

Министерство образования и науки Российской Федерации

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

 

Факультет информационных технологий

 

Кафедра вычислительной техники

 

 

 

Задание на курсовую работу

 

Исходные данные:                Размерность матрицы: 70×70;          

                  Тип сортировки: по возрастанию;

Область сортировки: каждая строка;

Значение элементов матрицы: тип word.

 

Перечень подлежащих разработке вопросов:

1. раскрыть проблему сортировки больших массивов данных;
2. исследовать различные методы сортировок, оценить их эффективность;
3. реализовать программу, производящую сортировку матриц различными методами;
4. реализовать программный интерфейс;
5. провести сравнительный анализ временной эффективности разработанных алгоритмов.

 

Перечень графического материала:

Рисунки, схемы, таблицы, отражающие сравнительные характеристики методов сортировок.

      

 

 

 

 

 

 

Дата выдачи задания “___”_________________20____г.

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

старший преподаватель                                  Медведев В. А.

Исполнитель

студент группы 11ИВТ(б) ВМК                    Кожевников Н.В.

Срок защиты работы “__”__________________20___г. 

Содержание

 

Введение………………………………………………………...………………..……4

1 Проблематика методов сортировок………………………………………………..5

1. Классификация алгоритмов сортировок……………………………………......5
2. Оценка алгоритмов сортировок…………………………………………….…...5

1.3 Анализ алгоритмов сортировок…………………………………………………6

1. Пузырьковая сортировка...………………………………………………….....6
2. Сортировка выбором………………………………………………...................8
3. Сортировка вставками…………………………………………………………8
4. Сортировка Хоара……………………………………………………………...9
5. Сортировка Шелла.…………………………………………………………...10
6. Поразрядная сортировка……………………………………………………...12
2. Разработка программы сортировки матрицы…………………………………...14
1. Типы переменных и файлов……………………………………………………14
2. Разработка интерфейса программы……………………………………………14
3. Разработка программы, реализующей сортировку матрицы………………...14
4. Сравнительный анализ разработанных алгоритмов сортировок…………….16

Заключение…………………………………………………………………………...17

Список использованных источников……………………………………………….18

Приложение А Листинг программы…………………….………………………….19

Приложение Б Схема алгоритма работы разработанных методов сортировок….23

Приложение В Структурная схема работы программы .………………………….27

Приложение Г Контрольный  пример работы с программой…………………..….28

 

Введение

Зачем нужна сортировка? Ответ простой: если данные не упорядочены, то найти что-либо можно только путем  последовательного перебора всех элементов.  Насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти компьютера, во многом зависит скорость выполнения и простота алгоритмов, предназначенных для их обработки.

Хотя в словарях слово  «сортировка» определяется как процесс  разделения объектов по виду или сорту, в программировании оно используется в гораздо более узком смысле, обозначая такую перестановку предметов, при которой они располагаются  в порядке возрастания или  убывания.

Некоторые из наиболее важных областей применения сортировки:

1. решение задачи группирования: нужно собрать вместе все элементы с одинаковыми значениями некоторого признака. Например, имеется 10000 элементов, расположенных в случайном порядке, причем значения многих из них равны, и нужно переупорядочить их так, чтобы элементы с равными значениями занимали соседние позиции;
2. поиск общих элементов в двух или более группах: если эти группы рассортировать в одном и том же порядке, то можно отыскать в них все общие элементы за один последовательный просмотр групп без возвратов;
3. поиск информации по значениям ключей: с помощью сортировки можно сделать результаты обработки данных более удобными для восприятия человеком.[1]

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Проблематика методов сортировок

1. Классификация алгоритмов сортировок

Количество  алгоритмов сортировки достаточно велико. В настоящее время их число, включая экзотические и мало распространенные алгоритмы, приближается к сорока.[2] Все эти алгоритмы можно классифицировать по нескольким признакам:

1. в зависимости от того, сортируются данные в оперативной памяти машины или во внешнем запоминающем устройстве, сортировка бывает внутренней или внешней;
2. в зависимости от того, какая структура данных подвергается сортировке, может быть сортировка массива, связного списка, дерева (пирамиды), графа;
3. в зависимости от того, как структура данных меняется в процессе сортировки, может быть сортировка списка (если элементы структуры данных перемещаются) или сортировка таблицы адресов (если элементы не перемещаются, а сортируется имеющаяся или создаваемая таблица адресов). В таблицу адресов могут быть добавлены ключи, тогда получается сортировка таблицы ключей;
4. по особенностям функциональной реализации алгоритмы сортировки делятся на группы:
1. основные:

1.   сортировка перестановками;
2. сортировка выбором;
3. сортировка вставками;

2. неосновные:

1. сортировка подсчетом;
2. сортировка слиянием;
3. распределяющая сортировка;

5. по широте применения − универсальные (большинство перечисленных выше групп алгоритмов) и алгоритмы для конкретных случаев, не универсальные;

6. по признаку перестановки совпадающих данных в процессе сортировки − алгоритмы, не меняющие порядок следования совпадающих ключей (такие алгоритмы называют "устойчивыми" или "стабильными"), например, сортировка вставками, и меняющие порядок следования ("неустойчивые");

ж)      по времени работы.[3]

Возможны  также некоторые другие принципы разделения алгоритмов сортировки.

 

 

2. Оценка алгоритмов сортировок

Существует много различных  алгоритмов сортировки. Все они имеют  свои положительные стороны, но общие  критерии оценки алгоритма сортировки

таковы: быстрота сортировки информации в среднем, быстрота сортировки информации в худшем и лучшем случаях, естественное или неестественное поведение алгоритма,  происходит ли перестановка элементов с одинаковыми ключами.

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

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

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

Чтобы понять, почему переупорядочивание элементов с одинаковыми ключами  имеет определенное значение, можно представить себе базу данных почтовой рассылки, упорядоченную по главному ключу и подключу. Главным ключом является почтовый индекс, а в пределах одного почтового индекса записи упорядочены по фамилии. При добавлении в список нового адреса и пересортировке списка порядок подключей (то есть фамилий внутри почтовых индексов) не должен меняться. Для гарантии, что это не произойдет, алгоритм сортировки не должен обменивать ключи с одинаковым значением.[4, 5]

 

3. Анализ алгоритмов сортировки
1. Пузырьковая сортировка

Самый простой алгоритм группы обменных сортировок (или сортировок перестановками) получил название пузырьковой сортировки. Этот алгоритм считается самым простым из универсальных, одновременно являясь одним из самых медленных. Пузырьковая сортировка заключается в сравнении соседних элементов и, при необходимости, в их перестановке. При неубывающем упорядочении элементы "всплывают" как пузырьки каждый до своего уровня (а другие элементы одновременно "тонут").