|
|
5,6 лабы. Алгоритмы сортировки и поиска
МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра «РАПС»
отчет
по лабораторной работе №5,6
по дисциплине «Программирование и основы алгоритмизации»
Тема: Алгоритмы сортировки и поиска.
Студент гр. 7401
|
|
Серебрянский М.Ю.
|
Преподаватель
|
|
Калинин А.В.
|
Санкт-Петербург
2018
Алгоритмы сортировки
1. Сортировка тестового массива данных
Для каждого алгоритма сортировки проверили кол-во сравнений и перестановок на тестовом массиве. Все результаты примерно одинаковы, однако, немного лучше всех себя показал алгоритм быстрой сортировки.
2. Исследование и анализ эффективности различных алгоритмов сортировки
Провели эксперименты для всех размерностей и алгоритмов и получили, что на неупорядоченных данных лучше всего себя показывает быстрая сортировка. При чем, на большом кол-ве данных быстрая сортировка выполняется гораздо быстрее. Уже на при 25000 элементах кол-во сравнений и перестановок быстрой сортировки больше других алгоритмов в 1000 раз.
Все остальные алгоритмы показали себя примерно одинаково.
3. Исследование зависимости эффективности алгоритмов сортировки от харак-тера входных данных
Упорядоченные данные:
Здесь лучше всего себя показали сортировки прямым включением и шейкерная сортировка, они всего сравнили элементы столько раз, сколько было элементов в массиве.
Быстрая же сортировка, которая себя хорошо показала на неупорядоченных данные, здесь показала себя хуже упомянутых выше сортировок.
Данные, упорядоченные в обратном порядке:
Здесь лучше всего себя показала быстра сортировка, опять опередив всех остальных во много раз.
Наблюдения:
Сортировка тестового массива данных.
44 Яблоки
55 Апельсины
12 Бананы
42 Груши
94 Сливы
18 Виноград
6 Абрикосы
67 Вишня
|
Массив из 8 элементов.
Тип сортировки
|
Сортировка прямым включением
|
Сортировка прямым выбором
|
Сортировка прямым обменом
|
Шейкерная сортировка
|
Быстрая сортировка
|
Число сравнений
|
20
|
28
|
28
|
22
|
22
|
Число перестановок
|
20
|
5
|
15
|
15
|
5
| Сортировка заданного массива данных.
02 Уфа
58 Пенза
05 Махачкала
95 Краснодар
07 Нальчик
13 Саранск
19 Абакан
66 Екатеринб
45 Курган
68 Тамбов
77 Москва
78 Спб
71 Тула
74 Челябинск
61 Ростов
|
|
Массив из 15 элементов.
Тип
сортировки
|
Сортировка прямым включением
|
Сортировка прямым выбором
|
Сортировка прямым обменом
|
Шейкерная сортировка
|
Быстрая сортировка
|
Число сравнений
|
37
|
105
|
105
|
48
|
69
|
Число перестановок
|
32
|
11
|
23
|
23
|
12
|
Исследование и анализ эффективности различных алгоритмов сортировки. -
Для получения данных об эффективности работы 5-ти алгоритмов проведём
Тип сортировки
|
Сортировка прямым включением
|
Сортировка прямым выбором
|
Сортировка прямым обменом
|
Шейкерная сортировка
|
Быстрая сортировка
|
Время, с
|
Размерность
|
25 000
|
0,593
|
1,092
|
1,606
|
1,186
|
0,015
|
50 000
|
2,402
|
4,305
|
6,489
|
4,680
|
0,016
|
75 000
|
5,226
|
9,719
|
14,695
|
10,452
|
0,032
|
100 000
|
9,297
|
17,410
|
26,240
|
18,595
|
0,047
|
Исследование зависимости эффективности алгоритмов сортировки от характера входных данных.
Неупорядоченный массив:
Тип сортировки
|
Сортировка прямым включением
|
Сортировка прямым выбором
|
Сортировка прямым обменом
|
Шейкерная сортировка
|
Быстрая сортировка
|
Время, с
|
9,329
|
17,347
|
26,723
|
18,766
|
0,047
|
Число сравнений
|
2510009512
|
4999950000
|
4999950000
|
3326561666
|
2209799
|
Число перестановок
|
2509909517
|
99987
|
2500435786
|
2493396535
|
384998
|
Упорядоченный по возрастанию массив:
Тип сортировки
|
Сортировка прямым включением
|
Сортировка прямым выбором
|
Сортировка прямым обменом
|
Шейкерная сортировка
|
Быстрая сортировка
|
Время, с
|
0,000
|
17,800
|
17,129
|
0,000
|
0,016
|
Число сравнений
|
99999
|
4999950000
|
4999950000
|
99999
|
1602638
|
Число перестановок
|
0
|
0
|
0
|
0
|
0
|
Упорядоченный по убыванию массив:
Тип сортировки
|
Сортировка прямым включением
|
Сортировка прямым выбором
|
Сортировка прямым обменом
|
Шейкерная сортировка
|
Быстрая сортировка
|
Время, с
|
18,705
|
17,270
|
18,657
|
18,892
|
0,015
|
Число сравнений
|
4999949824
|
4999950000
|
4999950000
|
4999949999
|
1602708
|
Число перестановок
|
4999945097
|
52197
|
4999945024
|
4999945121
|
50000
|
|
Алгоритмы поиска:
Поиск_в_тестовом_массиве_данных'>1. Поиск в тестовом массиве данных
Проверили все алгоритмы поиска. На тестовом массиве данных поиск осуществляется быстрее всего интерполяционным поиском.
2. Исследование и анализ эффективности различных алгоритмов поиска
Линейный поиск:
Выполняет шагов столько, сколько элементов расположено до заданного ключа. Никак не опирается на структуру массива. Может работать на неупорядоченных данных.
Двоичный поиск:
Требует чтобы данные были отсортированы. При этом условии поиск выполняется гораздо быстрее линейного, но сама сортировка занимает больше времени, чем линейный поиск. Поэтому данный вид поиска не целесообразно использовать на неотсортированных данных.
Интерполяционный поиск:
Данный поиск также, как и двоичный требует чтобы данные в массиве, в котором производится поиск были отсортированы. этот алгоритм поиска работает еще быстрее, чем двоичный. Однако этот алгоритм также нецелесообразно использовать, если массив данных, в котором производится поиск не должен быть упорядочен.
В текстовом массиве. «Виноград»
1 Персики
3 Черешня
6 Абрикосы
12 Бананы
18 Виноград
42 Груши
44 Яблоки
55 Апельсины
67 Вишня
94 Сливы
95 Лимоны
98 Арбузы
99 Дыни
|
Тип
сортировки
|
Линейный поиск
|
Двоичный поиск
|
Интерполяционный поиск
|
Ключ поиска
|
18
|
Число шагов
|
5
|
3
|
3
|
В заданном массиве. «Mazda»
Тип
сортировки
|
Линейный поиск
|
Двоичный поиск
|
Интерполяционный поиск
|
Ключ поиска
|
87
|
Число шагов
|
16
|
4
|
2
|
66 Volkswagen
89 Nissan
90 Toyota
10 Kyron
45 Lincoln
23 Maybach
55 Hammer
87 Mazda
91 Bentley
89 Fiat
34 Renault
9 Chrysler
87 Volvo
78 Ferrari
45 Lamborgini
89 Bugatti
|
|
Вывод. Самыми эффективными методами пояска являются: двоичный и интерполяционный. Интерполяционный поиск удобно использовать в программах с достаточно равномерным распределением данных. На практике, интерполяционный поиск часто быстрее бинарного, так как с вычислительной стороны их отличают лишь применяемые арифметические операции.
|
|
Так как размер нашей базы не велик, мы реализовали сортировку прямым выбором, которая на небольшом массиве данных ведет себя практически так же, как и быстрая сортировка.
Поиск
В данной части программы мы линейным поиском ищем элемент базы данных, название которого совпадает с названием прибора, введенного пользователем.
Вывод
В этой лабораторной работе мы познакомились с различными видами сортировок и поиска. Также мы реализовали алгоритмы сортировки и поиска в нашем проекте. |
|
|
Скачать 27.11 Kb.