Исследование и сравнение методов сортировки

1.

КУРСОВАЯ РАБОТА
ПО ДИСЦИПЛИНЕ:
«МЕТОДЫ ПРОГРАММИРОВАНИЯ»
НА ТЕМУ:
«ИССЛЕДОВАНИЕ И СРАВНЕНИЕ МЕТОДОВ СОРТИРОВКИ:
БЛОЧНАЯ СОРТИРОВКА И БЫСТРАЯ СОРТИРОВКА;
И МЕТОДОВ ПОИСКА: ДВОИЧНЫЙ ПОИСК В
УПОРЯДОЧЕННЫХ МАССИВАХ И ДВОИЧНОЕ
ОТСЛЕЖИВАНИЕ И ПОИСК»
Выполнил: студент группы КА-22-05
Третьяков Егор Сергеевич
Научный руководитель: доцент Крючков Алексей Вячеславович
Москва, 2023 г.

2.

ЦЕЛЬ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ
Цель работы: исследовать и сравнить методы сортировки: блочной сортировки и быстрой
сортировки; и методов поиска: двоичный поиск в упорядоченных массивах и двоичное
отслеживание и поиск.
Задачи курсовой работы:
1.
Исследование методов сортировки: блочной сортировки и быстрой сортировки;
2.
Исследование методов поиска: двоичный поиск в упорядоченных массивах и двоичное
отслеживание и поиск;
3.
Практическое воплощение исследованных методов сортировки на языке
программирования Python и тестирование этих методов на различных типах данных;
4.
Практическое воплощение исследованных методов поиска на языке программирования
Python и тестирование этих методов на различных типах данных.
2

3.

ГЛАВА 1. МЕТОДЫ СОРТИРОВКИ
Блочной сортировки (bucket sort) метод блочной сортировки в чём-то
аналогичен
методу
сортировки
слиянием. Согласно его алгоритму,
необходимо разбить массив на ряд
блоков (или карманов), размер
которых определяется характером
значений в массиве.
Быстрая сортировка (quick sort) (была
разработана
английским
информатиком Тони Хоаром (Tony
Hoare) в 1960 году в основу алгоритма
данного метода сортировки положен
принцип разбиения массива на 2 части с
помощью некоторого элемента массива,
который называется пивотом. Выбрав
его положение следует в левую часть
перемещать элементы, значения которых
меньше его, а в правую часть –
элементы, значения которых больше или
равны его значению.
3

4.

МЕТОДЫ СОРТИРОВКИ
Блочная сортировка (BucketSort) эффективна в случае равномерно
распределенных данных и часто используется для работы с большими объемами
данных, особенно в сценариях внешней сортировки. Ее преимущества включают
возможность распараллеливания, простую реализацию и подход к внешней
сортировке.
С другой стороны, быстрая сортировка (QuickSort) известна своей высокой
производительностью и эффективностью на практике. Она обеспечивает
адаптивность к предварительно отсортированным данным, не требует
дополнительной памяти и поддается параллелизации. Так же, алгоритм
чувствителен к выбору опорного элемента и не является устойчивым.
4

5.

ГЛАВА 1. МЕТОДЫ ПОИСКА
Двоичный поиск (полуинтервальный
поиск, или бинарный поиск) – это
такой процесс, при котором целевое
значение
ищут
только
в
отсортированном массиве, алгоритм
сравнивает элемент в середине списка с
искомым. Если искомый элемент
меньше, чем найденный, то алгоритм
продолжает поиск в первой половине
списка, если больше – в правой
половине.
Двоичное отслеживание и поиск – это
алгоритм поиска, который основан на
постепенном
увеличении
на
2k
диапазона поиска в массиве, при
каждом проходе цикла k увеличивается
на единицу. Когда искомый элемент
оказывается в диапазоне поиска, то
элемент
находится
с
помощью
бинарного поиска.
5

6.

МЕТОДЫ ПОИСКА
Двоичный поиск и двоичное отслеживание и поиск представляют собой
эффективные алгоритмы для поиска элементов в упорядоченных массивах или
списках. Оба метода основаны на стратегии деления диапазона, что обеспечивает
быструю сходимость и логарифмическую сложность алгоритма.
Двоичный поиск в упорядоченных массивах предоставляет значительное
увеличение эффективности. Его высокая эффективность с временной сложностью
O(log n) и эффективность использования памяти делают его привлекательным для
больших объемов упорядоченных данных. Однако его требование упорядоченности
данных, неуниверсальность для неупорядоченных данных и неустойчивость к
дубликатам могут быть ограничивающими факторами.
6

7.

ГЛАВА 2. МЕТОДЫ СОРТИРОВКИ. БЛОЧНАЯ СОРТИРОВКА.
Рис. 2 – программная реализация блочной сортировки на языке
программирования Python
Рис. 1 – пример работы блочной сортировки
7

8.

МЕТОДЫ СОРТИРОВКИ. БЫСТРАЯ СОРТИРОВКА.
Рис. 4 – программная реализация быстрой сортировки на языке
программирования Python.
Рис. 3 – блок-схема быстрой сортировки
8

9.

РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ МЕТОДОВ СОРТИРОВКИ
Таблица 1
Таблица 2
Результаты реализации программы внешних сортировок
Название
сортировки
Вид тестовых
данных
Объединение
Пересечение
Быстрая
сортировка
Блочная
сортировка
Разность
Количество
сравнений
54195
4661
21377
Результаты реализации программы внутренних сортировок
Время
Количество выполнени
перестаново
я
к
Сортировк
и (мс)
5.81312179
56834
5654297
0.65708160
4989
40039062
2.31289863
22531
5864258
Симметрическа
я
разность
43962
46263
Объединение
40000
43927
Пересечение
2254
2738
Разность
7604
2738
Название
сортировки
Быстрая
сортировка
Блочная
сортировка
4.70805168
1518555
7.64608383
1787109
0.49304962
158203125
1.57999992
37060547
9
Вид тестовых
данных
Количество
сравнений
Количество
перестаново
к
Список
69818
72614
Матрица
67096
69891
Список
350684
350684
Матрица
692374
697364
Время
выполнения
Сортировки
(мс)
10.467052459
716797
10.229110717
773438
66.892147064
20898
68.933010101
31836

10.

ГЛАВА 2. МЕТОДЫ ПОИСКА. ДВОИЧНЫЙ ПОИСК В УПОРЯДОЧЕННЫХ МАССИВАХ.
Рис. 6 – программная реализация двоичного поиска в
упорядоченных массивах на языке программирования
Python.
Рис. 5 – блок-схема двоичного поиска в упорядоченных
массивах.
10

11.

МЕТОДЫ ПОИСКА. ДВОИЧНОЕ ОТСЛЕЖИВАНИЕ И ПОИСК.
Рис. 7 – пример работы двоичного отслеживания и поиска.
Рис. 8 – программная реализация двоичного
отслеживания и поиска на языке программирования Python.
11

12.

РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ МЕТОДОВ ПОИСКА
Таблица 3
Таблица 4
Результаты реализации алгоритма двоичного поиска
в упорядоченных массивах
Результаты реализации алгоритма двоичного
отслеживания и поиска
Название метода поиска
Время
выполнения
поиска всех слов
Количество циклов
Название метода поиска
Время
выполнения
поиска всех слов
Количество циклов
Двоичный поиск
294 мс.
121 395
Двоичное отслеживание и
поиск
553 мс.
1 289 890
12

13.

РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ МЕТОДОВ ПОИСКА
Рис.9 - результат работы двоичного поиска.
Рис.10 - результат работы двоичного отслеживания и поиска.
13

14.

ЗАКЛЮЧЕНИЕ
В ходе данной лабораторной работы была достигнута цель и выполнены
поставленные задачи.
Быстрая сортировка обеспечивает высокую производительность и
эффективность, особенно на практике, но может быть чувствительна к выбору
опорного элемента. В то время как блочная сортировка эффективна при работе с
равномерно
распределенными
данными
и
обеспечивает
возможность
распараллеливания, что делает ее подходящей для работы с большими объемами
информации.
Двоичный поиск обладает универсальностью и простотой реализации, подходя
для различных типов данных, но требует равномерного распределения. Следящий
двоичный поиск, использующий интерполяцию, быстро сходится при равномерном
распределении, но может проявить неэффективность при неравномерных данных и
требует более сложной реализации.
14

15.

English Русский Rules