ФГБОУ ВПО «Сыктывкарский государственный университет»

Институт точных наук и информационных технологий

Кафедра информационной безопасности

Допустить к защите

Зав. кафедрой, к.ф.-м.н., доцент

__________Л.С. Носов

«___»_______2012г.

Курсовая работа по дисциплине

«Методы программирования и прикладные алгоритмы»

Методы сортировки.

Научный руководитель:

к.ф.-м.н., доцент _____ Ю.В. Гольчевский

«___»_______2012г.

Исполнитель:

студент группы 123 ________ Б. А. Нестеров

«___»_______2012г.

Сыктывкар, 2012

Содержание

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

Глава 1. Алгоритмы сортировок

1.1 Сортировка методом обмена.……………………………………………..…………… 5

1.2 Сортировка с помощью выбора…………………………………………………………6

1.3 Сортировка методом Хоара ………………………………………...…………………. 7

1.4 Сортировка методом Уильямса-Флойда……...………………………………………..9

Глава 2. Эффективность методов

2.1 Сравнение методов сортировки………………………………………………………..12

2.2 Применение методов……………………………………………………………………14

Глава 3. Графический интерфейс

3.1 Стартовое окно………………………………………………………………………… 15

3.2 Построение неотсортированных прямоугольников.………………..………………… 15

3.3 Сортировка отсортированных прямоугольников…………………………………… 16

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

Библиографический список …………………………………………………...………….….. 18

Приложения…...………………………………………………………………………………...19

Введение

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

В общем сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты.

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

Цель моей работы: оценить эффективность методов сортировки обменами, вставками, метода Хоара и метода Уильмса-Флойда.

Для достижения поставленной цели необходимо решить следующие задачи:

1. Изучить алгоритмы сортировки обменами, сортировки вставками(Пузырьком), сортировки методом Хоара(Быстрая) и метода Уильямса-Флойда(Пирамидальная).

2. Реализовать и наглядно продемонстрировать эти методы в следующей задаче:

1. Сгенерировать N пар точек (x₁, y₁) и (x₂, y₂) случайным образом.

2. Вычислить площади прямоугольников, построенных по этим парам точек. Пронумеровать эти прямоугольники.

3. Отсортировать эти прямоугольники по возрастанию площади. Использовать сортировку обменами, вставками, метод Хоара, метод Уильямса-Флойда.

4. Оценить эффективность этих методов для большого количества элементов, измерив время работы.

5. *Построить прямоугольники, закрашенные разным цветом.