Реферат по дициплине: «Структуры данных и алгоритмы»

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

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

Чтобы оценить время работы алгоритмов использовалась программа, которая формировала массив случайных целых чисел на отрезке [0,50000] целых чисел, а затем сортировала этот массив каждым из алгоритмов сортировки. Были получены результаты для массивов с количеством элементов от 1000 до 20000 с интервалом 1000. В таблице 3 представлены усредненные результаты, полученные в ходе их проведения.
Таблица 3.
Время сортировки

Количество элементов		Метод сортировки
		Обменами , мс	Вставками, мс		Пирамиды, мс	Быстрая, мс
1000	764		468	31		16
2000	3339		3308	93		31
3000	7363		5366	94		109
4000	13244		6131	172		63
5000	20561		10920	219		94
6000	28891		12449	297		109
7000	43024		20639	296		187
8000	50841		23400	328		218
9000	63929		31746	421		281
10000	83803		35334	468		234
11000	94365		42198	499		297
12000	…		50372	530		296
13000	…		59592	593		312
14000	…		67970	671		374
15000	…		78109	811		359
16000	…		88561	827		437
17000	…		103974	889		452
18000	…		109543	1014		515
19000	…		124223	1226		546
20000	…		138122	1326		561

Проанализировав полученные результаты, можно сделать несколько выводов. Несложно заметить, что наилучшую скорость работы показал алгоритм сортировки Хоара. Так же хорошую скорость показал метод сортировки Уильямса-Флойда. Когда количество элементов массива не превышало 50 000, упорядочивание происходило практически мгновенно, остальные алгоритмы показали не высокую скорость работы и применение их при разработке серьезных программ не допустимо.
Методы сортировки Уильямса-Флойда и Хоара это в своём роде улучшение алгоритмов выбора и обмена. Поэтому сравним их попарно.
На рисунке 1 представлен график зависимости времени работы от количества элементов методов обмена и выбора.

Кол-во
Р исунок 1. График зависимости времени работы от количества элементов методов обмена и выбора( синяя- метод обмена, красная - метод выбора).
Из рисунка 1 видно, что метод сортировки выбором работает быстрее для большого количества элементов.
На рисунке 2 представлен график зависимости времени работы от количества элементов методов Хоара и Уильямса-Флойда. Алгоритм Хоара или как его ещё называют алгоритм быстрой сортировки показал более высокую скорость и признан лучшим алгоритмов сортировки массивов из представленых.

Кол-во
Рисунок 2. График зависимости времени работы от количества элементов методов Хоара и Уильямса-Флойда(синий-Уильямса-Флойда, красный- Хоара).

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

Трудно назвать какой-то метод лучшим какой-то худшим. Для каждой ситуации нужно подобрать более удобный метод. Например метод сортировки обменами легко реализовать. И если нужно упорядочить небольшое количество элементов, то он более предпочтителен.
Метод сортировки Хоара достаточно трудно реализовать. Он работает по принципу рулетки и зависит от выбора граничного элемента. При неудачном выборе граничного числа он работает медленно.

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

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

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

Рисунок 3. Стартовое окно

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

Если после генерирования нажать кнопку построить, то прямоугольники нарисуются в неотсортированном порядке (рис.4).

Рисунок 4. Построение неотсортированных прямоугольников
3.3 Построение отсортированных прямоугольников
Если мы отсортировали прямоугольники по площадям любым из представленных методов, то после нажатия кнопки построить программа построит их в порядке возрастания (рис.5).

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

Заключение.

В ходе курсовой работы были выполнены следующие задачи.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.

1. 
   Н. Вирт Алгоритмы и структуры данных. – М.: Мир, 1939, 360 стр.
   
2. 
   Н. Вирт Алгоритмы + структуры данных = программы. – М.: Мир, 1997, 407 стр.
   
3. 
   Д.Кнут искусство программирования Том 3. – М:Вильямс, 2-е издание, 2002, 800 стр.
   
4. 
   http://INTUIT .ru – Интернет-Университет Информационных Технологий
   
5. 
   https:// revolution.allbest.ru