Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

lab2001 / АИСД / лаба1

.doc
Скачиваний:
29
Добавлен:
16.04.2013
Размер:
120.32 Кб
Скачать

Лабораторная работа №1 "Методы сортировки"

Данная лабораторная работа выполняется под управлением операционной системы Windows 3.11 или выше. Цель работы: исследование сложности различных алгоритмов сортировки целочисленных массивов в зависимости от исходных параметров этих массивов.

1. В результате измерения скорости сортировки массива из 3000 элементов и с диапазоном значений 3000 были установлены следующие результаты:

Название метода

Время, с

Быстрая Хоара

0,05

Естественная двухпутевым сливанием

0,06

Шелла

0,07

Бинарной вставкой

0,88

Интерполяционной вставкой

0,90

Простым выбором

1,64

Простой вставкой

2,36

Пузырьком

3,46

К быстрым методам были отнесены: Быстрая Хоара, Естественная двухпутевым сливанием, Шелла, Бинарной вставкой.

К медленным: Бинарной вставкой, Интерполяционной вставкой, Простым выбором, Простой вставкой, Пузырьком.

2. Исследование всех методов сортировки на их сложность.

Метод

500

1000

1500

2000

2500

1000

2000

4000

8000

16000

Быстрая Хоара

0

0

0,5

0,06

0,22

Естественная двухпутевым сливанием

0

0,5

0,11

0,22

0,50

Шелла

0

0,6

0,12

0,24

0,58

Бинарной вставкой

0,11

0,38

1,59

6,10

24,12

Интерполяционной вставкой

0,06

0,11

0,22

0,44

0,66

Простым выбором

0,06

0,22

0,44

0,83

1,26

Простой вставкой

0,06

0,22

0,64

1,10

1,71

Пузырьком

0,06

0,33

0,82

1,48

2,31

Или, если представлять в графическом виде:

Быстрая сортировка Хоара.

Естественная двухпутевым слиянием.

Шелла.

Бинарная вставка.

Простым выбором.

Простой вставкой.

Пузырьком.

4.Более подробное исследование метода Шелла.

1000

2000

5000

10000

20000

прямая

0

0,06

0,17

0,35

0,77

обратная

0

0,06

0,17

0,36

0,77

Разброс 1000

0

0,06

0,17

0,35

0,74

Разброс 20000

0

0,06

0,17

0,35

0,74

Уже упорядоч.

0

0

0

0

0

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

Все измерения проводились на компьютере оснащенном процессором intel P!!!-533B, со 128 Мб оперативной памяти. Использовалась операционная система Microsoft Windows98.

Работу выполнил студент гр. МП-38 Музыченко Максим.

Соседние файлы в папке АИСД